有依赖的背包问题

:::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)。

# 输入输出样例

输入

输出

1

2200

# 解题思路

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

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

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

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

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59


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