题解 | #【模板】分组背包#

题目链接

题目描述

给定 $N$ 件物品和一个最大可承重为 $W$ 的背包。所有物品被划分为若干个组，同一组中的物品是互斥的，即每组至多只能选择一件物品。第 $i$ 件物品的重量是 $w_i$ ，价值是 $v_i$ ，所属组别是 $g_i$ 。求解在不超过背包承重的前提下，选择若干物品使得总价值最大。

输入:

第一行输入两个整数 $N, W$ ，分别表示物品数量与背包容量。
接下来 $N$ 行，每行输入三个整数 $w_i, v_i, g_i$ ，描述第 $i$ 件物品的重量、价值与所属组别。

输出:

输出一个整数，代表在约束条件下可以获得的最大价值。

解题思路

本题是典型的 分组背包问题。其核心特点是：所有物品被分成若干组，每组内的物品相互冲突，最多只能选一个。

问题转化:
- 我们可以把每一组物品看作一个整体。对于每一组，我们的决策是：不选该组的任何物品，或者只选择该组中的某一个物品。
- 这将问题从对 $N$ 个物品的决策，转化为了对 $k$ 个组的决策。
状态定义:
- 我们定义一个一维数组 $dp$ ，其中 $dp[j]$ 表示在背包容量为 $j$ 的情况下，所能获得的最大价值。
状态转移:
- 状态转移的思路是，依次遍历每一个组，并用这个组内的物品来更新 $dp$ 数组。
- 假设我们正在处理第 $i$ 组，对于一个给定的容量 $j$ ，我们可以做出的决策有：
  - 不选第 $i$ 组的任何物品，此时最大价值就是 $dp[j]$ （由前 $i-1$ 组决定）。
  - 选择第 $i$ 组中的第 $k$ 件物品（重量 $w_k$ ，价值 $v_k$ ），前提是 $j \ge w_k$ 。此时的最大价值为 $dp[j - w_k] + v_k$ 。
- 我们需要遍历第 $i$ 组中的所有物品，找出能使 $dp[j]$ 最大的那个选择。
- 状态转移方程可以描述为： $dp[j] = \max(dp[j], \max_{k \in \text{group}_i} \{dp[j-w_k] + v_k \})$
遍历顺序:
- 首先，需要对物品按组进行预处理，将同一组的物品放在一起。
- 外层循环遍历每个组。
- 中层循环遍历背包容量 $j$ ，并且必须是 逆序遍历（从 $W$ 到 $0$ ）。这与01背包的原理相同，是为了保证在处理第 $i$ 组时，我们用来更新状态的 $dp[j-w_k]$ 是只考虑了前 $i-1$ 组的结果。
- 内层循环遍历当前组内的所有物品，进行决策。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct Item {
    int w, v;
};

int main() {
    int N, W;
    cin >> N >> W;

    map<int, vector<Item>> groups;
    int max_group_id = 0;
    for (int i = 0; i < N; ++i) {
        int w, v, g;
        cin >> w >> v >> g;
        groups[g].push_back({w, v});
        max_group_id = max(max_group_id, g);
    }

    vector<long long> dp(W + 1, 0);

    for (int i = 1; i <= max_group_id; ++i) {
        if (groups.count(i)) {
            for (int j = W; j >= 0; --j) {
                // 遍历组内物品做决策
                for (const auto& item : groups[i]) {
                    if (j >= item.w) {
                        dp[j] = max(dp[j], dp[j - item.w] + item.v);
                    }
                }
            }
        }
    }

    cout << dp[W] << "\n";
    return 0;
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static class Item {
        int w, v;
        Item(int w, int v) {
            this.w = w;
            this.v = v;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int W = sc.nextInt();

        Map<Integer, List<Item>> groups = new HashMap<>();
        int maxGroupId = 0;
        for (int i = 0; i < N; i++) {
            int w = sc.nextInt();
            int v = sc.nextInt();
            int g = sc.nextInt();
            groups.putIfAbsent(g, new ArrayList<>());
            groups.get(g).add(new Item(w, v));
            maxGroupId = Math.max(maxGroupId, g);
        }

        long[] dp = new long[W + 1];

        for (int i = 1; i <= maxGroupId; i++) {
            if (groups.containsKey(i)) {
                for (int j = W; j >= 0; j--) {
                    for (Item item : groups.get(i)) {
                        if (j >= item.w) {
                            dp[j] = Math.max(dp[j], dp[j - item.w] + item.v);
                        }
                    }
                }
            }
        }
        System.out.println(dp[W]);
    }
}

N, W = map(int, input().split())
groups = {}
for _ in range(N):
    w, v, g = map(int, input().split())
    if g not in groups:
        groups[g] = []
    groups[g].append((w, v))

dp = [0] * (W + 1)

for group_id in sorted(groups.keys()):
    items = groups[group_id]
    for j in range(W, 0, -1):
        for item_w, item_v in items:
            if j >= item_w:
                dp[j] = max(dp[j], dp[j - item_w] + item_v)

print(dp[W])

算法及复杂度

算法：动态规划 (分组背包)
时间复杂度： $O(N \cdot W)$ - 虽然是三层循环，但内两层循环的总迭代次数是 $\sum_{i=1}^{\text{num_groups}} |group_i| = N$ ，所以总复杂度是 $O(W \cdot N)$ 。
空间复杂度： $O(W + N)$ - 主要开销来自 $dp$ 数组和存储分组物品的容器。