【例9.16】分组背包

题目描述

一个最多能装 $V$ （ $V \leqslant 200$ ）公斤的背包， $N$ （ $N \leqslant 30$ ）件物品重量 $W_i$ 、价值 $C_i$ ，划分为 $T$ （ $T \leqslant 10$ ）组，每组最多选一件。第一行输入 $V, N, T$ ，随后 $N$ 行每行 $W_i, C_i, P$ （重量、价值、组号）；输出一行，为最大总价值。如样例输入 10 6 3 / 2 1 1 / 3 3 1 / 4 8 2 / 6 9 2 / 2 8 3 / 3 9 3，输出 20（选 $(3,3)$ 、 $(4,8)$ 、 $(3,9)$ ）。

思路

设 $dp[cap]$ 为容量不超过 $cap$ 的最大价值，三层循环：外层枚举组、容量倒序、内层枚举组内物品做 $dp[cap] = \max(dp[cap], dp[cap-W_j]+C_j)$ 。容量倒序让每个格子只读上一组的旧值，同组物品不会叠加，天然满足每组最多选一件； $dp[cap]$ 单调不减，答案即 $dp[V]$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:52
# update_at: 2026-09-30 02:52

import sys


def add_group(dp: list[int], group: list[tuple[int, int]], capacity: int) -> list[int]:
    """把一组互斥物品并入 dp，返回合并后的新价值表。

    dp[cap] 表示容量不超过 cap 时的最大价值，且只统计已处理完的组。
    新表的每个格子只读旧表：不选这一组（旧值 dp[cap]），或从旧表挑组内一件物品，
    所以组内任意两件物品都不可能在同一个格子里叠加，天然满足「最多选一件」。
    """
    # picks[cap]：这一组选某一件物品后能达到的价值；只查旧表（上一轮 dp），绝不同时查组内另一件
    picks = [
        [dp[cap - weight] + value for weight, value in group if weight <= cap]
        for cap in range(capacity + 1)
    ]
    return [max([old, *options]) for old, options in zip(dp, picks)]  # old = 这一组一件都不选


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    capacity, item_count, group_count = next(data), next(data), next(data)

    groups: list[list[tuple[int, int]]] = [[] for _ in range(group_count + 1)]
    for _ in range(item_count):
        weight, value, group = next(data), next(data), next(data)
        groups[group].append((weight, value))

    dp = [0] * (capacity + 1)
    for group in groups[1:]:
        dp = add_group(dp, group, capacity)

    print(dp[capacity])  # dp[cap] 单调不减，容量上限处就是答案


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:44
 * update_at: 2026-10-05 07:44
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXV = 205; // 背包容量上限
const int MAXN = 35;  // 物品数量上限

ll V, N, T;
ll w[MAXN], c[MAXN], grp[MAXN]; // 每件物品的重量、价值、所属组号
ll dp[MAXV]; // dp[cap]：只考虑已处理完的组、容量不超过 cap 时的最大价值

int main() {
    cin >> V >> N >> T;
    for (int i = 1; i <= N; i++)
        cin >> w[i] >> c[i] >> grp[i];

    // 分组背包：外层枚举组，容量倒序，最内层枚举组内物品
    // 容量倒序保证每轮转移只读「上一组处理完」的旧值，
    // 同组两件物品不会在同一个格子里叠加，天然满足每组最多选一件
    for (int g = 1; g <= T; g++)
        for (int cap = V; cap >= 0; cap--)
            for (int i = 1; i <= N; i++)
                if (grp[i] == g && w[i] <= cap)
                    dp[cap] = max(dp[cap], dp[cap - w[i]] + c[i]);

    // dp[cap] 关于 cap 单调不减，容量上限处就是答案
    cout << dp[V] << endl;
    return 0;
}

【例9.16】分组背包

目录

题目描述

思路

参考代码