$\LARGE\color{orange}{刷题日记(算法提高课)}$

我们将所有有依赖关系的物品看成一个物品组，那么这个物品组内的物品个数为 1 到 3 不等

设物品个数为 $n$ ，那么对于单个物品组而言，选择的可能性总数为 $2^{n-1}$

举例来说，现有物品 $a,\ p,\ q$，$p,\ q$ 是 $a$ 的附属，可能的选择有：

• $a$

• $a,\ p$

• $a,\ q$

• $a,\ p,\ q$

为了遍历所有的可能性，我们采取二进制枚举，即：

设物品个数为 $x$

for(int i = 0; i < 1 << x; i++)//枚举所有的选法，总共二的n次幂种
    for(int j = 0; j < x; j++)//对于每一种选法而言，我们找出具体选了哪个数
        if(i >> j & 1)//对相应的数进行处理

在这道题里面，我们将有依赖关系的物品都看成一个物品组

我们对每一个物品组都进行二进制处理，这就相当于是枚举组内的所有物品

因此，这就可以看成是分组背包问题

在具体实现上，由于每个物品都有体积和价值，还有物品编号，因此我们直接用 pair 来存储会更方便

当然，对于主件和附件的存储需要分开，由于同一个组件可能有多个附件，因此需要用 vector<pair> 来存储

完整代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 32000 + 10, M = 100;

typedef pair<int, int> PII;

PII master[M];

vector<PII> servent[M];

int f[N];
int n, m;

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
    {
        int v, p, q;
        cin >> v >> p >> q;
        if(!q) master[i] = {v, v * p};
        else servent[q].push_back({v, v * p});//将附件放在主件对应下标处
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= 0; j--)
        {
            for(int k = 0; k < 1 << servent[i].size(); k++)
            {
                int v = master[i].first, w = master[i].second;
                for(int t = 0; t < servent[i].size(); t++)
                    if(k >> t & 1)
                    {
                        v += servent[i][t].first;
                        w += servent[i][t].second;
                    }
                if(j >= v) f[j] = max(f[j], f[j - v] + w);//在物品组内部做选择
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}