https://www.cnblogs.com/violet-acmer/p/9852294.html
题解：
这道题是 “01”背包问题的变形。
如果不考虑买附件必须买相应的主件这一条件下，这就是单纯的 “01”背包问题。
那，这道题该如何做呢？
注意看一下题干，每个主件最多有 2 个附件，那这就容易些了，枚举所有的可能；
对于第 i 个主件，有以下五种可能：
(1):不选主件 i
(2):只选主件 i
(3):选主件 i + 附件1
(4):选主件 i + 附件2
(5):选主件 i + 附件1 + 附件2
从这五个中找到最大的价值组合，并和 dp[i-1][ j ]判断，取最大值，当然在选择附件时，需要满足当前价值可以容下所选择的总价值。
AC代码：
#include<iostream>
#include<cstdio>
using namespace std;
#define P pair<int ,int >
const int maxn=3.2e4+; int n,m;
int dp[][maxn];
P mainG[maxn];//存储主件信息
P touchG[][maxn];//touchG[i] : 存储主件 i 含有的附件信息
int total[];//total[i] : 主件 i 含有的附件个数
int Val(P p){
return p.first*p.second;
}
void Solve()
{
for(int i=;i <= m;++i)
{
P one=touchG[i][];
P two=touchG[i][];
for(int j=;j <= n;++j)
{
dp[i][j]=dp[i-][j];
if(j >= mainG[i].first)
dp[i][j]=max(dp[i][j],dp[i-][j-mainG[i].first]+Val(mainG[i]));
if(j >= mainG[i].first+one.first)
dp[i][j]=max(dp[i][j],dp[i-][j-mainG[i].first-one.first]+Val(mainG[i])+Val(one));
if(j >= mainG[i].first+two.first)
dp[i][j]=max(dp[i][j],dp[i-][j-mainG[i].first-two.first]+Val(mainG[i])+Val(two));
if(j >= mainG[i].first+one.first+two.first)
dp[i][j]=max(dp[i][j],dp[i-][j-mainG[i].first-one.first-two.first]+Val(mainG[i])+Val(one)+Val(two));
}
}
printf("%d\n",dp[m][n]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i <= m;++i)
{
int v,p,q;
scanf("%d%d%d",&v,&p,&q);
if(!q)
mainG[i]=P(v,p);
else
touchG[q][++total[q]]=P(v,p);
}
Solve();
}
二维dp
#include<iostream>
#include<cstdio>
using namespace std;
#define P pair<int ,int >
const int maxn=3.2e4+; int n,m;
int dp[maxn];
P mainG[maxn];//存储主件信息
P touchG[][maxn];//touchG[i] : 存储主件 i 含有的附件信息
int total[];//total[i] : 主件 i 含有的附件个数
int Val(P p){
return p.first*p.second;
}
void Solve()
{
for(int i=;i <= m;++i)
{
P one=touchG[i][];
P two=touchG[i][];
for(int j=n;mainG[i].first != && j >= ;--j)
{
if(j >= mainG[i].first)
dp[j]=max(dp[j],dp[j-mainG[i].first]+Val(mainG[i]));
if(j >= mainG[i].first+one.first)
dp[j]=max(dp[j],dp[j-mainG[i].first-one.first]+Val(mainG[i])+Val(one));
if(j >= mainG[i].first+two.first)
dp[j]=max(dp[j],dp[j-mainG[i].first-two.first]+Val(mainG[i])+Val(two));
if(j >= mainG[i].first+one.first+two.first)
dp[j]=max(dp[j],dp[j-mainG[i].first-one.first-two.first]+Val(mainG[i])+Val(one)+Val(two));
}
}
printf("%d\n",dp[n]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i <= m;++i)
{
int v,p,q;
scanf("%d%d%d",&v,&p,&q);
if(!q)
mainG[i]=P(v,p);
else
touchG[q][++total[q]]=P(v,p);
}
Solve();
}
一维dp
关于主件编号问题（踩坑了）：
m个物品，编号为 1~m，而不是按照主件的个数进行编号。
例如：
(正确编号)(错误编号)
2000 10
500 1 0 1 1
400 4 0 2
300 5 1 3
400 5 1 4
200 5 0 5
500 4 5 6
400 4 0 7
320 2 0 8
410 3 0 9
400 3 5 10
找这个BUG找了好几个小时，mmp，心累啊.................