题解：P1064 [NOIP 2006 提高组] 金明的预算方案
DeepSleep_Zzz
·
·
题解
begin
P1064 [NOIP 2006 提高组] 金明的预算方案
题目大意
给你一堆物品的价格和重要程度，这些物品分为主件和附件，其中每个主件最多有两个附件，求在给定价格内每件物品的价格与重要程度的乘积的总和最大是多少。
分析
这题看起来挺唬人的，其实扒了外皮就是个背包，只不过多了个主件附件的问题。
思路
既然买了附件就必须买主件，那我们不妨将它们绑定在一起，然后枚举每一个主件的购买方式。
对于每一次购买，只会出现以下 5 种购买方式：
- 什么都不买。
- 只买主件。
- 买主件和第一个附件。
- 买主件和第二个附件。
- 买主件和全部两个附件。
我们只要把这五种情况的价值套一下背包板子算出来，取一下最大值即可。
至于如何绑定主件和附件，我们可以定义一个数组 son_{i,3}，其中 son_{i,0} 表示其附件的个数（其实也可以不要，但是我太懒），son_{i,1} 表示其第一个附件的编号，son_{i,2} 同理。
动态转移方程
我们设 dp_j 为花费 j 元所能得到的最大答案，那么有：
dp_j=\max(dp_j,dp_{j-v_i}+v_i\times w_i)
$j$ 表示此时背包的容积（价格），从 $n$ 倒着枚举到 $0$。
不难发现，这玩意实际上就是一个 01 背包板子。
# Code
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m,v[70],w[70],c[70],dp[32010],son[70][3],q[70];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for (ll i=1;i<=m;i++)
{
cin>>v[i]>>w[i]>>q[i];
c[i]=v[i]*w[i]; // 只是因为我懒得写乘号
if (q[i]) son[q[i]][++son[q[i]][0]]=i; // 绑定
}
for (ll i=1;i<=m;i++) // 背包板子
{
for (ll j=n;j>=0;j--)
{
if (q[i]) continue; // 我们只考虑主件
if (j>=v[i]) // 够买主件
dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
if (son[i][1] && j>=v[i]+v[son[i][1]]) // 够买主件和附件1
dp[j]=max(dp[j],dp[j-v[i]-v[son[i][1]]]+c[i]+c[son[i][1]]);
if (son[i][2] && j>=v[i]+v[son[i][2]]) // 够买主件和附件2
dp[j]=max(dp[j],dp[j-v[i]-v[son[i][2]]]+c[i]+c[son[i][2]]);
if (son[i][0]>=2 && j>=v[i]+v[son[i][1]]+v[son[i][2]]) // 够买主件和全部附件
dp[j]=max(dp[j],dp[j-v[i]-v[son[i][1]]-v[son[i][2]]]+c[i]+c[son[i][1]]+c[son[i][2]]);
}
}
cout<<dp[n];
return 0;
}
```
**end**