TIP

今天真是狗血啊,一道题弄着这么长的时间,还没有搞得很透彻,虽然AC了。我要狠狠的记住它。

# 金明的预算方案

# 题目描述

金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过N元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:

主件 附件

电脑 打印机,扫描仪

书柜 图书

书桌 台灯,文具

工作椅 无

如果要买归类为附件的物品,必须先买该附件所属的主件。每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。金明想买的东西很多,肯定会超过妈妈限定的N元。于是,他把每件物品规定了一个重要度,分为5等:用整数1-5表示,第5等最重要。他还从因特网上查到了每件物品的价格(都是10元的整数倍)。他希望在不超过N元(可以等于N元)的前提下,使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品,编号依次为j1,j2,...,jk,则所求的总和为:

v[j1] * w[j1] + v[j2] * w[j2] + ... + v[jk] * w[jk]

请你帮助小明设计一个满足要求的购物清单。

# 输入格式

第一行,为里啷个正整数,用一个空格隔开:

n,m (其中n代表总钱数,m为希望购买物品的个数。n<32000,m<60) 从第2行到第m+1行,第j行给出了编号为j-1的物品的基本数据,每行有3个非负整数

v,p,q (其中v表示该物品的价格,p表示该物品的重要度,q表示该物品的主件还是附件。如果q=0,表示该物品为主件,如果q>0,表示该物品为附件,q是所属主件的编号。v<1000,1<=p<=5)

# 输出格式

一个正整数,为不超过总钱数的物品的价格与重要度乘积的总和的最大值(不超过200000)。

# 输入输出样例

输入

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出

2200

# 解题思路

首先一看到这道题的难度等级是普及+/提高,我就有想跳过去的感觉,然后看到标签里是背包类型的,想着尝试一把,就这样过去了一天。

这道题与01背包有很大的不同,因为它牵扯到了一件物品与另一件物品的依赖关系,只有购买了这一件物品,才有选择购买不购买另一件物品的权力。

在本题中,只有购买了主件,才能购买附件。那么我就在想,如何才能知道,主件有没有被选中呢?(即被购买)我首先想到了做标记,但是要怎么标记呢?假如说,我强制选择了这个主件,那么就说明这个主件我已经购买了,然后就可以选择购买不购买附件,但是对于在附件中选择一个最优的情况,只能用总钱数-主件的价格来进行购买,否则就有可能出现抛弃主件的可能性,不对,即使这样,也有可能出现抛弃主件的情况,当附件价格很低而重要度很高,这就行不通了。

然后我就想着,看能不能在进行选择主件的时候进行特殊操作,设置一个标记项,当标记为1时,就说明是对主件操作,对主件操作时,需要用总钱数-主件的价格去购买附件,我刚刚才想到这个方法也是不行的,但是测试数据还是过了,我满怀希望的提交上去,一个大零蛋。

这样也不行啊,还是看看题解吧,看到他们写的思路都差不多,因为附件只有2个,所以对于每一主件的选择至多有5种情况。第一个,不选这个主件。第二,只选择主件。第三,选择主件和第一个附件。第四,选择主件和第二个附件。第五,选择主件和两个附件。但是我想了很久都不知道,要怎么实现这么多种情况的选择呢?看到题解中都写到,分组背包,01背包,依赖背包,我又赶紧去了解了一下自己不熟悉的,看着看着就困了还小眯了一会。醒来继续看。依赖背包通常和分组背包一起使用,因为可以在这一组中把所有可能的策略都列举出来,分组背包就是在这一组中,只选择一个或者一个都不选,所以可以利用这一特点。

如何把所有可以选择的策略存储下来,我也想了很久,先开始我是把数据存储下来,然后再想怎么列举所有的情况,难道我还要来个不完全排列吗?不会的,最后我想到,主件还照以前那样存储,但是附件在存储之前,需要和主件、包括主件中已存在的附件都要去组合一次,这样所有的情况都可以一个个嵌套,所有的情况就出来了。

剩下的用分组背包的套路就能够实现了,但是还不知道分组背包是怎么运行的,为什么在一组中就只选择一个。还要好好弄弄。 下面就把代码贴出来。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Node
{
    int v;//代表价格
    int w;//代表价格与重要度的乘积
};
vector<Node> s[100];//用来存储的vector容器,下表组号
Node e;
int f[100000];//状态转移数组
int a[100];//编号与组号的映射数组
int main()
{
    int n, m;//n代表总钱数,m代表希望购买的物品个数
    cin >> n >> m;
    int t = 0;
    for (int i = 1; i <= m; i++)
    {
        int v, p, q;//v物品价格,p重要度,q主附件编号
        cin >> v >> p >> q;
        e.v = v;//价格
        e.w = p * v;//权重
        if (q == 0)//如果是主件直接往下一组存储
        {
            s[++t].push_back(e);
            a[i] = t;//保存编号对应的组号
        }
        else if (q > 0)//这也是最精妙的部分
        {
            Node E;
            int length = s[a[q]].size();
            for (int i = 0; i < length; i++)//将所有的情况都列举一遍
            {
                E.v = e.v + s[a[q]][i].v;
                E.w = e.w + s[a[q]][i].w;
                s[a[q]].push_back(E);
            }
        }
    }
    fill(f, f + 33000, 0);//状态转移数组初始值为0
    for (int k = 1; k <= t; k++)//组号
    {
        for (int i = n; i >= 0; i--)//钱数
        {
            for (auto it = s[k].begin(); it != s[k].end(); it++)//组中的所有策略
            {
                e = *it;
                if (i >= e.v)
                {
                    f[i] = max(f[i], f[i - e.v] + e.w);
                }
            }
        }
    }
    cout << f[n];//最大值
    return 0;
}