题解 P1064 【金明的预算方案】
Mutsumi_0114
2018-10-20 17:06:38
### “有依赖的背包问题” [(背包九讲)](https://www.kancloud.cn/kancloud/pack/70131)
大部分题解做法，是将本题每项主件与其附件的每种搭配情况在递推式内枚举，使得代码递推式部分冗长臃肿，且不适于附件较多的情况。
本题属于 非树形有依赖的背包问题（只有两类物品：主件，附件），下面给出具体解题思路。
* 注意，真正的树型依赖背包更为复杂，以至于可计算的数据范围骤减
首先我们注意到对于每一个主件，有很多种购买的方案：可以不买，可以只买主件，或者买主件外加几种附件，当附件个数较少的时候枚举就可以 $AC$。
例如这样：
(上图来自 @ShawnZhou 的题解)
本做法中，我们先对每种主件的 **附件的集合** 进行一次 $01$ 背包处理，就可以先求出 **对于每一种主件包括其附件的组合中，每种花费的最大价值**（读不懂的同学可以看后面解释）。
对于每一种主件的01背包处理：
```
for i：主件k的所有附件
for j：价值（0 ~ n-主件价值）
01背包递推
```
这样可以得到主件 $k$ 的附件中费用依次为 $0 \sim n-v[k]$ 时的相应最大价值 $f[0 \sim n-v[k]]$，那么我们就得到了主件 $k$ 及其附件集合的 $n-v[k]+1$ 种不同选择情况，其中费用为 $v[k]+t$ 的物品的价值就是 $f[t]+v[k]*p[k]$ 。
对于每一个主件处理出的情况，**在 $n-v[k]+1$ 种情况之中只能最多选择一种选入最终答案之中（把上面文字多读几遍吧）**，原问题便转化成一个分组背包问题。
如果你不知道分组背包的话：
```
for 所有的组k
for v = V ... 0
for 所有的i属于组k
f[v]=max{f[v],f[v-c[i]]+w[i]}
```
这题的分组背包部分应该是这样写的：
```
for 所有的主件数k
for j = n ... 0
for 所有的主件和附件的组合属于组k
f[j]=max{f[j],f[j-v[i]]+v[i]*p[i]}
```
上面就已经是具体思路了，实现需要比较多的数组存储结果，还有最容易错的一点是，本题的情况状态01背包计算需要使用 “恰好背包” （数组下标严格与花费价钱相等，详见代码注释）：
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct cas
{
int v,p,q;
}a[60],pat[60][60];
int n,m,t[60],V[60][10],P[60][10],cnt[60],f[32000],ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);//正常的读入
if(a[i].q)//如果这个物品是附件
{
t[a[i].q]++;
pat[a[i].q][t[a[i].q]].v=a[i].v;
pat[a[i].q][t[a[i].q]].p=a[i].p;
pat[a[i].q][t[a[i].q]].q=a[i].q;//把它存在相应的主件的分组中
}
}
for(int i=1;i<=m;i++)//01背包处理
{
if(t[i])//如果当前物品为主件
{
memset(f,-1,sizeof(f));//恰好背包的处理，-1表示不恰好取到此价值
f[0]=0;//恰好背包的处理
for(int j=1;j<=t[i];j++)
for(int k=n-a[i].v;k>=pat[i][j].v;k--)
if(f[k]<f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p && f[k-pat[i][j].v]!=-1)//恰好背包的判断
f[k]=f[k-pat[i][j].v]+pat[i][j].v*pat[i][j].p;//很平常的01状态转移
for(int j=0;j<=n-a[i].v;j++)
if(f[j]!=-1)//恰好背包的判断，这种附件组合满足题意
{
cnt[i]++;
V[i][cnt[i]]=j+a[i].v;
P[i][cnt[i]]=f[j]+a[i].v*a[i].p;//把此情况存在主件i的分组中，为分组背包做好处理
}
}
if(!a[i].q)//只买主件
{
cnt[i]++;
V[i][cnt[i]]=a[i].v;
P[i][cnt[i]]=a[i].v*a[i].p;//存储
}
}
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
for(int j=n;j>=0;j--)
for(int k=1;k<=cnt[i];k++)
if(j>=V[i][k])
f[j]=max(f[j],f[j-V[i][k]]+P[i][k]);//分组背包的计算
for(int i=0;i<=n;i++)
ans=max(ans,f[i]);
printf("%d",ans);//输出
return 0;
}
```
自制大数据练习：[U65320 Oak的预算方案](https://www.luogu.org/problemnew/show/U65320) (数据有误请及时反馈
------------
### 2019-8-3 更新：
在题目 $U65320$ 中, 收集到 @Jackpei 的优异解法, 供大家借鉴 (擅自修改了码风, 希望有助于各位阅读, 在此不作分析)：
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
int f[5000010],h[5000010];
struct node
{
int v,p,q;
}a[1010];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].v,&a[i].p,&a[i].q);
a[i].p*=a[i].v;
}
for(int i=1;i<=m;i++)
if(!a[i].q)
{
for(int j=1;j<a[i].v;j++)
h[j]=0;
for(int j=a[i].v;j<=n;j++)
h[j]=f[j-a[i].v]+a[i].p;
for(int j=1;j<=m;j++)
if(a[j].q==i)
for(int k=n;k>=a[i].v+a[j].v;k--)
h[k]=max(h[k],h[k-a[j].v]+a[j].p);
for(int j=a[i].v;j<=n;j++)
f[j]=max(f[j],h[j]);
}
printf("%d\n",f[n]);
return 0;
}
```