装箱问题3
http://codevs.cn/problem/3152/
设有n种物品，记作A1、A2、…、An，对应于每个Ai（1<=i<=n）都有一个重量Awi和价值Avi（重量和价值都为正整数）。另外，对应于每个Ai，都有一件可代替它的“代用品”Bi，Bi的重量和价值分别为Bwi和Bvi。
本题的任务是：选择这n件物品或其代用品的一个子集装进背包，使总重量不超过给定重量TOT，同时使总价值VAL最高。装填的第I步，要么装入Ai，要么装入Bi，要么Ai和Bi都不装。
第一行：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
只有一个数为最大的价值
4 20
8 20 12 31
2 3 9 20
13 31 11 12
8 9 13 36
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]); }
原文：http://www.cnblogs.com/TheRoadToTheGold/p/6358821.html