竞极 Ace

分组背包

分组背包

一、问题描述

有 NN 件物品，分成 TT 组，背包容量为 VV。第 kk 件物品的重量为 w[k]w[k]，价值为 v[k]v[k]。

每组最多选择一件物品，也可以不选。 求总重量不超过 VV 时，能够得到的最大总价值。

例题：P1308 分组背包。

题目样例中，背包容量为 1010，物品分为三组：

组别 组内物品（重量，价值）
1 (2,1)(2,1)、(3,3)(3,3)
2 (4,8)(4,8)、(6,9)(6,9)
3 (2,8)(2,8)、(3,9)(3,9)

分别选择 (3,3)(3,3)、(4,8)(4,8)、(3,9)(3,9)，总重量为 1010，总价值为 2020，这是最优方案。

01 背包限制每件物品最多选一次；分组背包还要求：同一组内的不同物品不能同时选择。

二、状态与转移

设 dp[i][j]dp[i][j] 表示：

只考虑前 ii 组物品，总重量不超过 jj 时，能够得到的最大总价值。

考虑第 ii 组，有两类选择：

  • 不选这一组，价值为 dp[i−1][j]dp[i-1][j]。
  • 选择组内某件物品 kk，价值为 dp[i−1][j−w[k]]+v[k]dp[i-1][j-w[k]]+v[k]，要求 w[k]≤jw[k]\le j。

设 GiG_i 为第 ii 组的物品集合，则：

$$\boxed{ dp[i][j]=\max\left( dp[i-1][j],\quad \max_{\substack{k\in G_i\\w[k]\le j}} \bigl(dp[i-1][j-w[k]]+v[k]\bigr) \right). }$$

如果组内没有能放下的物品，只保留不选这一组的情况。

所有选择都从第 i−1i-1 组的状态转移。 来源中没有第 ii 组的物品，加上当前物品后，就能保证这一组最多选一件。

初始时没有物品可选，因此 dp[0][j]=0dp[0][j]=0。最终答案为 dp[T][V]dp[T][V]。

三、一维优化：改变枚举顺序

用一维数组 dp[j] 保存状态，循环顺序为：

枚举组别 → 倒序枚举容量 → 枚举组内物品。

固定容量 jj，枚举这一组选哪件物品，取最大值后再更新 dp[j]：

for (int i = 1; i <= T; ++i) {
    for (int j = V; j >= 0; --j) {
        int best = dp[j];  // 不选第 i 组
        for (int k : group[i]) {
            if (j >= w[k]) {
                best = max(best, dp[j - w[k]] + v[k]);
            }
        }
        dp[j] = best;
    }
}

当 w[k]>0w[k]>0 时，j−w[k]<jj-w[k]<j。由于容量倒序枚举，较小容量还没有在本轮更新，因此 dp[j-w[k]] 保存的是上一组的状态。

容量循环必须放在组内物品循环的外层。 如果对组内每件物品分别做一次普通的 01 背包，仍可能同时选中同组的多件物品。例如，一组中只有 (2,3)(2,3) 和 (3,4)(3,4)，容量为 55 时，答案应该是 44，不能把两件都选上得到 77。

为什么这里使用 best？

如果所有物品的重量都大于 00，可以省去 best。 保持上述循环顺序，在组内直接更新即可：

dp[j] = max(dp[j], dp[j - w[k]] + v[k]);

因为来源容量严格小于 jj，更新 dp[j] 不会影响组内其他物品的转移来源。

但本题允许 w[k]=0w[k]=0，此时来源就是 dp[j]。例如，同组有两件重量为 00、价值为 55 的物品，初始 dp[j]=0，直接更新会让 dp[j] 先变成 55，再变成 1010，错误地选择了同组的两件物品。

因此，本题参考代码使用临时变量 best 记录最大值，组内枚举结束后才写回 dp[j]，保证所有候选都读取上一组的状态。best 用于处理零重量这一边界情况，并非所有分组背包题都必须使用。

四、参考代码

例题输入第一行为 V,N,TV,N,T，接下来 NN 行，每行输入一件物品的重量、价值和组别，即 Wk,Ck,PkW_k,C_k,P_k。代码中用 w[k]、v[k] 保存重量和价值，用 group[p] 保存第 pp 组的物品编号。

数据范围：V≤200V\le200、N≤50N\le50、T≤10T\le10，0≤Wk≤V0\le W_k\le V、0≤Ck≤1000\le C_k\le100、1≤Pk≤T1\le P_k\le T。

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

const int MAX_N = 55;
const int MAX_V = 205;
const int MAX_T = 15;

int V, n, T;
int w[MAX_N], v[MAX_N];
vector<int> group[MAX_T];
int dp[MAX_V];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> V >> n >> T;
    for (int k = 1; k <= n; ++k) {
        int p;
        cin >> w[k] >> v[k] >> p;
        group[p].push_back(k);
    }

    for (int i = 1; i <= T; ++i) {
        for (int j = V; j >= 0; --j) {
            int best = dp[j];  // 不选第 i 组
            for (int k : group[i]) {
                if (j >= w[k]) {
                    best = max(best, dp[j - w[k]] + v[k]);
                }
            }
            dp[j] = best;
        }
    }

    cout << dp[V] << '\n';
    return 0;
}

全局数组初始值为 00，对应允许不选任何物品。最多选择 1010 件物品，每件价值最多为 100100，因此 int 足以保存答案。

五、复杂度

每组枚举 V+1V+1 个容量，每件物品在每个容量下考虑一次，时间复杂度为 O((N+T)(V+1))O((N+T)(V+1))。

DP 数组占用 O(V)O(V) 空间，加上物品和分组信息，总空间复杂度为 O(V+N+T)O(V+N+T)。