python/C++专题课程/背包九讲/TestProject/6_GroupPackage.cpp

#include <bits/stdc++.h>

using namespace std;
/**
 6. 分组背包
    1）问题：
    有n件物品和一个容量为v的背包。
    第i件物品的费用是c[i]，价值是w[i]。
    这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。
    求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
    2）输入：
    测试用例数
    物品数 背包容量 组数g(组号范围：0 ~ g-1)
    第i件物品的ci wi gi(所属组号)
 */
using namespace std;
#define maxV 1000
#define maxG 100
#define maxN 100

int main(void) {
    int cases, n, v, g, gi;
    int f[maxV];
    int ci[maxN], wi[maxN];
    freopen("../6.txt", "r", stdin);
    cin >> cases;
    while (cases--) {
        memset(f, 0, sizeof(f));
        cin >> n >> v >> g;
        vector<vector<int> > gMap(g);
        for (int i = 0; i < n; i++) {
            cin >> ci[i] >> wi[i] >> gi;
            gMap[gi].push_back(i);
        }

        for (int i = 0; i < g; i++) {
            for (int j = v; j >= 0; j--) {
                for (int k = 0; k < gMap[i].size(); k++) {
                    if (j >= ci[gMap[i][k]])
                        f[j] = max(f[j], f[j - ci[gMap[i][k]]] + wi[gMap[i][k]]);
                }
            }
        }
        cout << f[v] << endl;
    }
}