一、题目链接：
二、题目大意：
给定总钱数
n
n
n
和可供选择的
m
m
m
个物品，物品之间构成主从关系，如果要买附属品，则必须购买他的前置物品，也就是主物品。每个物品有价格、重要性和主从关系：
v
i
,
p
i
,
q
i
v_i,p_i,q_i
v
i
,
p
i
,
q
i
。当
q
i
=
0
q_i=0
q
i
=
0
时，自己便是主物品。
现在要求在限定钱数为
n
n
n
的条件下，使得最后购买物品得到的权重
f
(
v
,
p
)
=
∑
i
=
1
m
v
i
×
p
i
f(v,p)=\sum_{i=1}^{m}v_{i}\times p_{i}
f
(
v
,
p
)
=
∑
i
=
1
m
v
i
×
p
i
最大，并输出最大值。
三、题目分析：
-
很显然这是一个
背包问题
的变种，所以方法在第一时间就确定下来了，我们采用
DP
DP
D
P
的方式来完成这道题。 -
由于题目中构成主从依赖关系，如果不选择主物品，那么附属物品也不能选择。所以相当于我们选择物品的时候是一组一组进行的。状态转移的时候便可以分组转移了，这便是一个典型的
分组背包
问题。 -
因为存在整组不选，或者选则一定选主物品，所以我们应当在转移和状态中体现这一点。
-
根据我们上面的结论可以得到以下最核心的状态转移方程：
dp
[
i
]
[
j
]
[
1
]
=
m
a
x
(
d
p
[
i
]
[
j
]
[
1
]
,
d
p
[
i
]
[
j
−
g
o
o
d
s
[
i
]
[
k
]
.
v
a
l
]
[
1
]
+
g
o
o
d
s
[
i
]
[
k
]
.
w
h
o
l
e
)
dp[i][j][1]=max(dp[i][j][1],dp[i][j-goods[i][k].val][1]+goods[i][k].whole)
d
p
[
i
]
[
j
]
[
1
]
=
ma
x
(
d
p
[
i
]
[
j
]
[
1
]
,
d
p
[
i
]
[
j
−
g
oo
d
s
[
i
]
[
k
]
.
v
a
l
]
[
1
]
+
g
oo
d
s
[
i
]
[
k
]
.
w
h
o
l
e
)
-
dp
[
i
]
[
j
]
[
1
]
dp[i][j][1]
d
p
[
i
]
[
j
]
[
1
]
表示前
ii
i
组，背包容量为
jj
j
，选择了
ii
i
组的主物品的最大收益。 -
go
o
d
s
[
i
]
[
k
]
.
v
a
l
goods[i][k].val
g
oo
d
s
[
i
]
[
k
]
.
v
a
l
表示第
ii
i
组第
kk
k
个物品的价格。 -
go
o
d
s
[
i
]
[
k
]
.
w
h
o
l
e
goods[i][k].whole
g
oo
d
s
[
i
]
[
k
]
.
w
h
o
l
e
表示第
ii
i
组第
kk
k
个物品的价格和重要性的乘积。
-
四、正解程序
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long ll;
struct node
{
ll val;//价格
ll p;//重要性
ll q;//主件
ll whole;
ll zhu;
}num[100];
vector<node> goods[100];
node basic[100];
ll n,m,count1=0;
ll dp[100][32000][2];//前i组，容量为j，选了还是没选
int main()
{
memset(dp,0x80,sizeof(dp));
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&num[i].val,&num[i].p,&num[i].q);
num[i].whole=num[i].val*num[i].p;
if(num[i].q==0)
{
num[i].zhu=(++count1);
basic[count1]=num[i];
}
}
for(ll i=1;i<=m;i++)
{
if(num[i].q!=0)
{
ll temp=num[num[i].q].zhu;
goods[temp].push_back(num[i]);
}
}
ll ans=0;
dp[0][0][0]=dp[0][0][1]=0;
for(ll i=1;i<=count1;i++)
{
for(ll j=0;j<=n;j++)
{
dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);//处理不选择第i组的情况
if(j<basic[i].val)
continue;
dp[i][j][1]=max(dp[i-1][j-basic[i].val][1],dp[i-1][j-basic[i].val][0])+basic[i].whole;//选择第i组，先处理主物品
ans=max(ans,max(dp[i][j][0],dp[i][j][1]));
}
for(ll k=0;k<goods[i].size();k++)//遍历副物品
{
for(ll j=n;j>=goods[i][k].val;j--)
{
dp[i][j][1]=max(dp[i][j][1],dp[i][j-goods[i][k].val][1]+goods[i][k].whole);
ans=max(ans,dp[i][j][1]);
}
}
}
printf("%lld\n",ans);
return 0;
}