题目内容

P1064

大意:金明有 N 元,想买 M 种物品,每个物品有价格 v_i 和重要度 p_i,有些物品是附件,必须要买主件才能买附件,求最大的 \sum v_ip_i

解题思路

“暴力”的正解

在这里问题的本质是不变的,仍是一个 0-1 背包问题,但不同的是加上了从属条件,也就是有依赖的背包问题。

由于一个主件最多有 2 个附件,因此可以考虑递推的时候暴力枚举。

开两个二维数组 v_{i,j} 表示第 i 个物品的第 j 个附件的价格(j=0 即为主件),p_{i,j} 表示第 i 个物品的第 j 个附件的重要程度。读入的时候进行处理即可。

然后当递推的时候,就存在 5 种选择:
1. 不选
2. 只要主件
3. 主+附件1
4. 主+附件2
5. 都要

根据当前枚举到的背包容量是否够即可。然后由于书写量太大容易出错,所以这里使用 lambda 表达式,具体见代码,转移方程与 0-1 背包的并无多大差别

#include <cstdio>
#include <algorithm>
using std::max;

int f[32010],v[70][3],p[70][3],aux[70],n,m;
//f 为递推数组, v,p 见上述,aux[i] 表示第 i 个物品拥有的附件个数

int main()
{
    scanf("%d %d",&n,&m);
    int _v,_p,q;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&_v,&_p,&q);
        if(!q)//如果是主件
            v[i][0]=_v,p[i][0]=_p;//直接搞
        else//否则是附件
            v[q][++aux[q]]=_v,p[q][aux[q]]=_p;//加到对应主件的后面去
    }
    for(int i=1;i<=m;i++)//开始递推
        for(int j=n;j>=v[i][0];j--)//熟悉的 0-1 背包
        {
            auto cost=[i](int x){return v[i][0]+v[i][x];};
            auto cost3=[i](){return v[i][0]+v[i][1]+v[i][2];};
            auto pdc=[i](int x){return v[i][x]*p[i][x];};
            //cost(x) 表示主件与第 x 个附件的价格之和
            //cost3() 表示主件与所有附件的价格之和
            //pdc(x) 表示第 x 个附件(0为主件)的价格与重要度的乘积
            f[j]=max(f[j],f[j-v[i][0]]+pdc(0));//第一个
            if(j>=cost(1))//如果可选第一个附件
                f[j]=max(f[j],f[j-cost(1)]+pdc(0)+pdc(1));//判断哪个更大
            if(j>=cost(2))//如果可选第二个附件
                f[j]=max(f[j],f[j-cost(2)]+pdc(0)+pdc(2));//同理
            if(j>=cost3())//如果都可以要
                f[j]=max(f[j],f[j-cost3()]+pdc(0)+pdc(1)+pdc(2));//那么都要
        }
    printf("%d\n",f[n]);//输出即可
    return 0;
}

真正正解(背包九讲)

刚才的方法很不错,但显然,当附件的数量多起来(刚才最多 2 个),数据变大之后,第一种方法就 gg 了,所以这里引出了背包九讲种使用的正解做法

最后修改日期:2020年2月22日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。