这是2006提高组的一道背包问题，这道题原来这就是有依赖的背包的模板题啊。
题意为一个01背包，但是有些物品是附件，也就是必须要买附件对应的主件，题目告诉我们每个主件只有0,1,2个附件所以产生了五种情况：1.只买主件 2.买主件+附件1 3.买主件+附件2 4.都买 5.不买。
那么第一步便是判断是否为主件，不是则存到主件的名下，这里开一个二维的消耗和价值数组，[i[[0]存储主件信息，[i][1],[i][2]分别存附件信息。然后再分情况去进行状态转移求最值，再加一个小剪枝。第四次提交后AC。
1.熟练掌握有依赖性的背包模板
2.有n个附件，则策略有2^n+1个选择
3.预处理一定要思路严谨，方便后续操作
4.有的时候一维数组记录不了，看看范围，开个二维数组记录也是可以的，找好主件
代码
// #include<iostream> #include<cmath> #include<algorithm> #include<cstdio> #include<string> #include<cstring> #define N 100001 using namespace std; int n,T; int f[N];//映射的主件 int m,v,p; long long value[N][5],weight[N][5]; long long dp[N]; int flag[N]; int main(){ //有依赖的背包~ cin>>T>>n; for(int i=1;i<=n;i++){ flag[i]=1; } for(int i=1;i<=n;i++){ cin>>m>>v>>p; if(p>0) f[i]=p; else if(p==0) f[i]=i; //只买主件、主件+附件1，主件+附件2，主件+附件1+附件2，不买 if(i==f[i]){ weight[i][0]=m;//本身 value[i][0]=m*v; } else{//附件 if(flag[p]==1){//是第一个附件 weight[p][1]=m; value[p][1]=v*m; flag[p]=2; } else if(flag[p]==2){//是第二个附加 weight[p][2]=m; value[p][2]=v*m; } } } dp[0]=0; for(int i=1;i<=n;i++){ if(weight[i][0]>0){ for(int j=T;j>=weight[i][0];j--){ if(j>=weight[i][0]){ dp[j]=max(dp[j],dp[j-weight[i][0]]+value[i][0]);//只买主件 } if(j>=weight[i][1]+weight[i][0]){ //只买附件一和.. dp[j]=max(dp[j],dp[j-weight[i][1]-weight[i][0]]+value[i][1]+value[i][0]); } if(j>=weight[i][2]+weight[i][0]){ //只买附件二和.. dp[j]=max(dp[j],dp[j-weight[i][2]-weight[i][0]]+value[i][2]+value[i][0]); } if(j>=weight[i][1]+weight[i][2]+weight[i][0]){ //都买 dp[j]=max(dp[j],dp[j-weight[i][1]-weight[i][2]-weight[i][0]]+value[i][1]+value[i][2]+value[i][0]); } } } } printf("%d",dp[T]); return 0; }