分组背包问题+依赖背包问题

对于选物品来说，不是每个物品独立的，而是如果要选某个物品，必须要买附带的物品。

我们可以将所有带依赖的物品看成不同的组。由于已知条件给定了每组物品不多，所以我们可以枚举每个组的所有可以选择的情况：

$ 时间复杂度O(4NM)$

参考文献

算法提高课

AC代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int, int> PAIR;
const int N = 60, M = 32000 + 10;

PAIR mas[N];//存主件
vector<PAIR> ser[N];//存主件的附件
int f[M];
int n, m;



int main(){
    //读入
    cin >> m >> n;
    for (int i = 1 ; i <= n ; i ++){
        int v, w, q;
        cin >> v >> w >> q;
        if (!q) mas[i] = {v, v * w};
        else ser[q].push_back({v, v * w});
    }


    for (int i = 1 ; i <= n ; i ++){
        for (int j = m ; j >= 0 ; j --){
            //枚举所有组合的方案,2的k次方个方案
            for (int k = 0 ; k < 1 << ser[i].size(); k ++){
                int v = mas[i].first, w = mas[i].second;
                for (int u = 0 ; u < ser[i].size() ; u ++){
                    if (k >> u & 1){
                        v += ser[i][u].first;
                        w += ser[i][u].second;
                    }
                }
                if (j >= v) f[j] = max(f[j], f[j - v] + w);
            }
        }
    }
    cout << f[m];
    return 0;
}