题解 P1064 【金明的预算方案】

· · 题解

“有依赖的背包问题” (背包九讲)

大部分题解做法，是将本题每项主件与其附件的每种搭配情况在递推式内枚举，使得代码递推式部分冗长臃肿，且不适于附件较多的情况。

本题属于 非树形有依赖的背包问题（只有两类物品：主件，附件），下面给出具体解题思路。

首先我们注意到对于每一个主件，有很多种购买的方案：可以不买，可以只买主件，或者买主件外加几种附件，当附件个数较少的时候枚举就可以 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背包计算需要使用 “恰好背包” （数组下标严格与花费价钱相等，详见代码注释）：

#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的预算方案 (数据有误请及时反馈

2019-8-3 更新：

在题目 U65320 中, 收集到 @Jackpei 的优异解法, 供大家借鉴 (擅自修改了码风, 希望有助于各位阅读, 在此不作分析)：

#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;
}