codevs 3152 装箱问题3

时间：2021-01-18 19:23:20

装箱问题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[][],v[][],f[];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

     scanf("%d%d%d%d",&w[i][],&v[i][],&w[i][],&v[i][]);

    for(int i=;i<=n;i++)

     for(int j=m;j>;j--)

      for(int k=;k<=;k++)

       {

             if(j<w[i][k]) continue;

             f[j]=max(f[j],f[j-w[i][k]]+v[i][k]);

       }

    printf("%d",f[m]);

}

相关文章