这题是依赖背包。
首先说明分组背包和依赖背包的区别：“分组背包”=“依赖背包”-“01背包”。
至于预处理可以参见分组背包的处理方法。
设计状态：dp[i]代表花费i元可以获得的最大价值。
转移方程：因为“分组背包”=“依赖背包”-“01背包”，所以“金明的预算方案”=“依赖背包”=“01背包”+“分组背包”。分类如下：
（1）01背包：money一定是够的，不用if判断 dp[j]=max(dp[j],dp[j-aw[i]]+av[i]);
（2）选择主件和第一个附件（且第一个附件存在） dp[j]=max(dp[j],dp[j-aw[i]-bw[1][i]]+av[i]+bv[1][i]);
（3）选择主件和第二个附件（且第二个附件存在） dp[j]=max(dp[j],dp[j-aw[i]-bw[2][i]]+av[i]+bv[2][i]);
（4）选择主件和两个附件（且两个附件都存在） dp[j]=max(dp[j],dp[j-aw[i]-bw[1][i]-bw[2][i]]+av[i]+bv[1][i]+bv[2][i]);
#include<bits/stdc++.h> using namespace std; const int N=32000+5; int m,n,v,p,q,aw[N],av[N],bw[5][N],bv[5][N],dp[N]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&v,&p,&q); if(q==0) aw[i]=v,av[i]=p*v; else { bw[0][q]++; bw[bw[0][q]][q]=v; bv[bw[0][q]][q]=v*p; } } for(int i=1;i<=n;i++) for(int j=m;j>=aw[i];j--) { dp[j]=max(dp[j],dp[j-aw[i]]+av[i]); if(j>=aw[i]+bw[1][i]) dp[j]=max(dp[j],dp[j-aw[i]-bw[1][i]]+av[i]+bv[1][i]); if(j>=aw[i]+bw[2][i]) dp[j]=max(dp[j],dp[j-aw[i]-bw[2][i]]+av[i]+bv[2][i]); if(j>=aw[i]+bw[1][i]+bw[2][i]) dp[j]=max(dp[j],dp[j-aw[i]-bw[1][i]-bw[2][i]]+av[i]+bv[1][i]+bv[2][i]); } printf("%d\n",dp[m]); return 0; }
原文：https://www.cnblogs.com/Siv0106/p/11721987.html