python/C++专题课程/背包九讲/TestProject/7_DependOnPackage.cpp

#include <bits/stdc++.h>

using namespace std;
/**
 7. 有依赖的背包
    1）题目：
    这种背包问题的物品间存在某种“依赖”的关系。
    也就是说，i依赖于j，表示若选物品i，则必须选物品j。
    为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；
    另外，没有某件物品同时依赖多件物品。
    2）输入：
    测试用例数
    物品数 背包大小
    第i个物品的ci wi di(依赖物品的编号，-1为不依赖其他物品)
 */
#define maxV 1000
#define maxG 100

int main(void) {
    int cases, n, v, ci[maxV], wi[maxV], di, f[maxV];
    freopen("../7.txt", "r", stdin);
    cin >> cases;
    while (cases--) {
        memset(f, 0, sizeof(f));
        cin >> n >> v;

        // group[i]空表示i号物品有依赖，因此存放到其他组里
        // 只有一个元素表示i号物品既无依赖也不被依赖
        // 有多个元素表示i号物品被依赖，这里自己的编号i也被存放进group[i]
        vector<vector<int> > groups(n);

        // 读入数据并储存起来
        for (int i = 0; i < n; i++) {
            cin >> ci[i] >> wi[i] >> di;
            if (di == -1) groups[i].push_back(i);
            else groups[di].push_back(i);
        }

        // 对每个有多个元素的组进行01背包
        for (int i = 0; i < n; i++) {
            if (groups[i].size() > 1) {
                vector<int> giOri; //group[i]的拷贝，排除i本身
                int newV = v - ci[i];

                // 复制group[i]中的元素，排除i
                for (int j = 0; j < groups[i].size(); j++) {
                    if (groups[i][j] != i)
                        giOri.push_back(groups[i][j]);
                }

                // 把等效物品组存入group[i]中
                groups[i].clear();
                groups[i].resize(newV + 1, 0);
                for (int j = 0; j < giOri.size(); j++) {
                    for (int k = newV; k >= 0; k--) {
                        if (ci[giOri[j]] <= k) {
                            groups[i][k] = max(groups[i][k], groups[i][k - ci[giOri[j]]] + wi[giOri[j]]);
                        }
                    }
                }
            }
        }

        // 进行分组背包
        for (int i = 0; i < n; i++) {
            if (groups[i].size() == 0) continue;
            else if (groups[i].size() == 1) { // i物品无依赖且不被依赖
                for (int j = v; j >= 0; j--) {
                    if (j >= ci[i])
                        f[j] = max(f[j], f[j - ci[i]] + wi[i]);
                }
            } else { // i物品被依赖, i组第k个物品的cost为k + ci[i], weight为group[i][k] + wi[i]
                for (int j = v; j >= 0; j--) {
                    for (int k = 0; k < groups[i].size(); k++) {
                        if (j >= k + ci[i])
                            f[j] = max(f[j], f[j - k - ci[i]] + groups[i][k] + wi[i]);
                    }
                }
            }
        }

        cout << f[v] << endl;
    }
}