题目内容
大意：金明有 N 元，想买 M 种物品，每个物品有价格 v_i 和重要度 p_i，有些物品是附件，必须要买主件才能买附件，求最大的 \sum v_ip_i
解题思路
“暴力”的正解
在这里问题的本质是不变的，仍是一个 0-1 背包问题，但不同的是加上了从属条件，也就是有依赖的背包问题。
由于一个主件最多有 2 个附件，因此可以考虑递推的时候暴力枚举。
开两个二维数组 v_{i,j} 表示第 i 个物品的第 j 个附件的价格（j=0 即为主件），p_{i,j} 表示第 i 个物品的第 j 个附件的重要程度。读入的时候进行处理即可。
然后当递推的时候，就存在 5 种选择：
1. 不选
2. 只要主件
3. 主+附件1
4. 主+附件2
5. 都要
根据当前枚举到的背包容量是否够即可。然后由于书写量太大容易出错，所以这里使用 lambda 表达式，具体见代码，转移方程与 0-1 背包的并无多大差别
#include <cstdio>
#include <algorithm>
using std::max;
int f[32010],v[70][3],p[70][3],aux[70],n,m;
//f 为递推数组， v，p 见上述，aux[i] 表示第 i 个物品拥有的附件个数
int main()
{
scanf("%d %d",&n,&m);
int _v,_p,q;
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&_v,&_p,&q);
if(!q)//如果是主件
v[i][0]=_v,p[i][0]=_p;//直接搞
else//否则是附件
v[q][++aux[q]]=_v,p[q][aux[q]]=_p;//加到对应主件的后面去
}
for(int i=1;i<=m;i++)//开始递推
for(int j=n;j>=v[i][0];j--)//熟悉的 0-1 背包
{
auto cost=[i](int x){return v[i][0]+v[i][x];};
auto cost3=[i](){return v[i][0]+v[i][1]+v[i][2];};
auto pdc=[i](int x){return v[i][x]*p[i][x];};
//cost(x) 表示主件与第 x 个附件的价格之和
//cost3() 表示主件与所有附件的价格之和
//pdc(x) 表示第 x 个附件（0为主件）的价格与重要度的乘积
f[j]=max(f[j],f[j-v[i][0]]+pdc(0));//第一个
if(j>=cost(1))//如果可选第一个附件
f[j]=max(f[j],f[j-cost(1)]+pdc(0)+pdc(1));//判断哪个更大
if(j>=cost(2))//如果可选第二个附件
f[j]=max(f[j],f[j-cost(2)]+pdc(0)+pdc(2));//同理
if(j>=cost3())//如果都可以要
f[j]=max(f[j],f[j-cost3()]+pdc(0)+pdc(1)+pdc(2));//那么都要
}
printf("%d\n",f[n]);//输出即可
return 0;
}
真正正解（背包九讲）
刚才的方法很不错，但显然，当附件的数量多起来（刚才最多 2 个），数据变大之后，第一种方法就 gg 了，所以这里引出了背包九讲种使用的正解做法
留言