题目描述

题目描述
如果要买归类为附件的物品，必须先买该附件所属的主件。

每个主件可以有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]（其中*为乘号）

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

输入样例

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

输出样例
2200

题解 (DP,分组背包问题)

可以将每个主件及其附件看作一个物品组，记主件为 pp，两个附件为 a,ba,b，则最多一共有4种组合：

p 
p,a 
p,b 
p,a,b

这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作一个物品，那么问题就变成了分组背包问题。可以参考AcWing 9. 分组背包问题。

在枚举四种组合时可以使用二进制的思想，可以简化代码。

时间复杂度

分组背包的时间复杂度是物品总数 * 总体积，因此总时间复杂度是 O(Nm)O(Nm)。

C++代码

#include <iostream>
#include <vector>

using namespace std;
const int N = 70, M = 32010;
int n, m;
typedef pair<int, int> PII;
PII master[N];
vector<PII> sv[N];
int f[M];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int v, w, q;
        cin >> v >> w >> q;
        if (!q) master[i] = {v, v * w};
        else sv[q].push_back({v, v * w});
    }
    for (int i = 1; i <= n; i++) {
        if (master[i].first) {
            for (int j = m; ~j; j--) {
                for (int k = 0; k < 1 << sv[i].size(); k++) {
                    int v = master[i].first, w = master[i].second;
                    for (int u = 0; u < sv[i].size(); u++) {
                        if (k >> u & 1) {
                            v += sv[i][u].first;
                            w += sv[i][u].second;
                        }
                    }
                    if (j >= v)
                        f[j] = max(f[j], f[j - v] + w);
                }
            }
        }
    }
    cout << f[m] << endl;

    return 0;
}