题意：有钱sum，给出n组选择，每种选择有m个物品w，要买物品先必须买盒子，物品价格为w[i]，价值p[i]。
然后给出每种选择的一些物品的价格还有价值求取得最大值。
物品依赖于盒子。
按照背包九讲的做法：
先对每组选择里的所有物品进行0-1背包处理，但背包容量为（总容量-盒子容量）；
然后跟上一组的状态比较来决定这一组选择 是选还是不选，取其中的较大值。
用dp[i][j]表示第i组背包容量为j时的最大价值。
在转移状态之前当前组选择的初始化：
for(j=0;j<q;j++)//q表示盒子的价格 dp[i][j]=-INF;//当钱<盒子价格时，无价值，注意不要赋值为0， 这题有 重量为0，但有价值的物品。
//例如 这组数据
1 10 11 1 0 11
盒子都买不起，所以输出0
但以上如果赋值为0，程序会输出11，是错误的。 for(j=q;j<=sum;j++) dp[i][j]=dp[i-1][j-q];//当钱>=盒子价格时，让前一组状态先买个盒子，买好盒子之后状态变为dp[i-1][j-q];
二维数组版：
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 1<<29 int n,sum,m,q; int w[11],p[11]; int dp[51][100003]; int main() { int i,j,x; while(~scanf("%d%d",&n,&sum)) { memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d%d",&q,&m); for(x=1;x<=m;x++) scanf("%d%d",&w[x],&p[x]); //注意初始化，上面已做出解释 for(j=0;j<=q;j++) dp[i][j]=-INF; for(j=q;j<=sum;j++) dp[i][j]=dp[i-1][j-q]; //按照背包九讲的做法，将当前组的物品进行0-1背包处理。 for(x=1;x<=m;x++) for(j=sum;j>=w[x];j--) dp[i][j]=max(dp[i][j],dp[i][j-w[x]]+p[x]); //跟上一组的状态进行比较，选择较大的值， //如果选dp[i][j]说明选了当前组的物品和盒子， //如果选dp[i-1][j]说明没有选当前组的物品和盒子。 for(j=0;j<=sum;j++) dp[i][j]=max(dp[i][j],dp[i-1][j]); } printf("%d\n",dp[n][sum]); } return 0; }
滚动数组版：
View Code
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 1<<29 int n,q; int w,p; int dp[100003],tmp[100003]; int main() { int i,&m); for(j=0;j<q;j++) tmp[j]=-INF; for(j=q;j<=sum;j++) tmp[j]=dp[j-q]; for(x=1;x<=m;x++) { scanf("%d%d",&w,&p);//写在循环内，边读入边对其进行0-1背包，省去了2个数组 for(j=sum;j>=w;j--) tmp[j]=max(tmp[j],tmp[j-w]+p); } for(j=0;j<=sum;j++) dp[j]=max(dp[j],tmp[j]); } printf("%d\n",dp[sum]); } return 0; }
