T2 金明的预算方案
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
2200把物品拆成主件，主件+1号附件，主件+2号附件，主件+2个附件来做分组背包
#include<cstdio> #include<algorithm> using namespace std; int n,m,u[61][4],p[61][4],q,f[32001]; int uu[61][3],pp[61][3]; void pre() { int uuu,ppp; for(int i=1;i<=m;i++) { scanf("%d%d%d",&uuu,&ppp,&q); if(!q) { u[i][0]=uuu; p[i][0]=ppp*uuu; uu[i][0]=uuu; pp[i][0]=ppp; } else { if(!u[q][1]) { uu[q][1]=uuu; pp[q][1]=ppp; u[q][1]=uu[q][0]+uu[q][1]; p[q][1]=uu[q][0]*pp[q][0]+uu[q][1]*pp[q][1]; } else { uu[q][2]=uuu; pp[q][2]=ppp; u[q][2]=uu[q][0]+uu[q][2]; p[q][2]=uu[q][0]*pp[q][0]+uu[q][2]*pp[q][2]; u[q][3]=uu[q][0]+uu[q][1]+uu[q][2]; p[q][3]=uu[q][0]*pp[q][0]+uu[q][1]*pp[q][1]+uu[q][2]*pp[q][2]; } } } } void dp() { for(int i=1;i<=m;i++) { if(!u[i][0]) continue; for(int j=n;j>=0;j--) for(int k=0;k<=3;k++) { if(j<u[i][k]) continue; f[j]=max(f[j],f[j-u[i][k]]+p[i][k]); } } printf("%d",f[n]); } int main() { scanf("%d%d",&n,&m); pre(); dp(); }
做这道题时出现的3个错误：
1、做的是01背包，导致出现选了主件+1号附件，又选主件+2号附件等错误。
2、分组背包三重循环应该先循环体积，再循环各组物品，否则出现上述错误。
3、u，uu数组，p，pp数组合二为一，混了。
原文：http://www.cnblogs.com/TheRoadToTheGold/p/6358816.html