首页 > 代码库 > codevs 3152 装箱问题3

codevs 3152 装箱问题3

装箱问题3

http://codevs.cn/problem/3152/

题目描述 Description

设有n种物品,记作A1、A2、…、An,对应于每个Ai(1<=i<=n)都有一个重量Awi和价值Avi(重量和价值都为正整数)。另外,对应于每个Ai,都有一件可代替它的“代用品”Bi,Bi的重量和价值分别为Bwi和Bvi。

本题的任务是:选择这n件物品或其代用品的一个子集装进背包,使总重量不超过给定重量TOT,同时使总价值VAL最高。装填的第I步,要么装入Ai,要么装入Bi,要么Ai和Bi都不装。

输入描述 Input Description

第一行:n TOT ,n<=100, TOT<=10000

第二行:AW1 A v1 B W1 Bv1

第三行:AW2 A v2 B W2 Bv2

……

第n+1行:AWn A vn B Wn Bvn

输出描述 Output Description

只有一个数为最大的价值

样例输入 Sample Input

4 20

8 20 12 31

2 3 9 20

13 31 11 12

8 9 13 36

样例输出 Sample Output

40

分组背包,每组分3个,不加,A,B

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,w[101][3],v[101][3],f[10001];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     scanf("%d%d%d%d",&w[i][1],&v[i][1],&w[i][2],&v[i][2]);
    for(int i=1;i<=n;i++)
     for(int j=m;j>0;j--)
      for(int k=0;k<=2;k++)
       {
             if(j<w[i][k]) continue;
             f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);
       }
    printf("%d",f[m]);
}

 

codevs 3152 装箱问题3