一本通-1272：【例9.16】分组背包

【题目描述】 一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

【输入】 第一行：三个整数，V(背包容量，V≤200)，N(物品数量，N≤30)和T(最大组号，T≤10)；

第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。

【输出】 仅一行，一个数，表示最大总价值。

【输入样例】 10 6 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3

【输出样例】 20

---

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

int v, n, t;
vector<int> weight(35), value(35);
vector<int> d(205);
vector<vector<int> > group(15, vector<int>(35));

int groupPack()
{
    for (int i = 1; i <= t; ++i) {
        for (int j = v; j >= 0; --j) {
            for (int k = 1; k <= group[i][0]; ++k) {
                int pos = group[i][k];
                if (j >= weight[pos]) {
                    d[j] = max(d[j], d[j - weight[pos]] + value[pos]);
                }
            }
        }
    }

    return d[v];
}



int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> v >> n >> t;
    int k;
    for (int i = 0; i < n; ++i) {
        cin >> weight[i] >> value[i] >> k;
        group[k][++group[k][0]] = i; //记录每个组的物品对应的序号
    }
    cout << groupPack() << endl;

    return 0;
}

分组背包的一个处理要点就是如何处理分组。用矩阵group记录这个组的物品对应的weight的下标，group[k][0]代表每个组内的元素的个数，剩下的就按01背包来处理就可以了。

t个组，背包容量为v，每个组的元素个数最多为q，时间复杂度$O(tvq)$。