HIGH89 【模板】分组背包

题目描述

给定 件物品与一只最大可承重为 的背包。所有物品被划分为若干个组，同一组中的物品是互斥的：对于每个组，你最多只能选择其中的一件物品。

第 件物品的重量是 ，价值是 ，所属组别为 。

请你在不超过背包承重 的前提下，选择若干物品使得总价值最大。

解题思路

这是一个经典的分组背包问题。它的特点是物品被分成了若干组，每组内的物品相互冲突，最多只能选择一个。

分组背包可以看作是0-1背包的一种扩展。在0-1背包中，我们对每个物品做决策：选或不选。在分组背包中，我们的决策单位变成了“组”：对于每一组，我们的决策是：

  1. 不选择该组中的任何物品。
  2. 选择该组中的某一个物品。

1. 状态定义

我们可以使用一维数组进行空间优化。定义 表示：当背包容量为 时，能获得的最大总价值。我们的最终目标是求解 。

2. 状态转移方程

解决分组背包问题的关键在于正确处理“组”这个维度。我们将外层循环设置为遍历每一个组，然后用组内的物品去更新 数组。

  • 外层循环：遍历每一个组 。
  • 中层循环：逆序遍历背包容量 （从 到 0）。
  • 内层循环：遍历组 内的每一个物品 （重量 ，价值 ）。

对于当前考虑的组 和背包容量 ，我们需要做出决策。决策是基于组内所有物品的。状态转移方程如下： (对于组 内的每一个物品 )

这里的关键在于中层循环（对容量 的遍历）必须是逆序的。为什么呢？

当我们处理第 组时，对于一个固定的容量 ，内层循环会尝试用组内所有物品去更新 。因为 是逆序的，所以在计算 dp[j - w_i] 时，我们所依赖的 dp 值一定是尚未被第 组物品更新过的状态（即只考虑了前 组物品的结果）。这保证了我们对于第 组，是在“不选”和“选择组内一个物品”之间做决策，从而确保了每组最多只选一个物品的约束。如果正序遍历，就会变成一个组内的完全背包问题，与题意不符。

3. 数据预处理

输入的物品是无序的，我们需要先将它们按照组别进行归类。可以使用 map (C++/Java) 或 dict (Python) 来存储每个组包含哪些物品。

算法总结

  1. 读入所有物品，并按组别存储。
  2. 初始化一个大小为 的 数组，所有元素为0。
  3. 外层循环遍历每一个组。
  4. 中层循环逆序遍历背包容量 (从 到 0)。
  5. 内层循环遍历当前组内的所有物品 。
  6. 如果当前容量 能容纳物品 （即 ），则应用状态转移方程更新 。
  7. 所有循环结束后， 即为答案。

代码实现

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

using namespace std;

struct Item {
    int w, v;
};

int main() {
    int n;
    int W;
    cin >> n >> W;

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

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

    // 遍历每一个组
    for (auto const& [group_id, items] : groups) {
        // 逆序遍历背包容量
        for (int j = W; j >= 0; --j) {
            // 遍历组内每一个物品，进行决策
            for (const auto& item : items) {
                if (j >= item.w) {
                    dp[j] = max(dp[j], dp[j - item.w] + item.v);
                }
            }
        }
    }

    cout << dp[W] << endl;

    return 0;
}

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

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<>();
        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));
        }

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

        // 遍历每一个组
        for (List<Item> items : groups.values()) {
            // 逆序遍历背包容量
            for (int j = W; j >= 0; j--) {
                // 遍历组内每一个物品，进行决策
                for (Item item : items) {
                    if (j >= item.w) {
                        dp[j] = Math.max(dp[j], dp[j - item.w] + item.v);
                    }
                }
            }
        }

        System.out.println(dp[W]);
    }
}

import collections

def main():
    n, W = map(int, input().split())
    
    groups = collections.defaultdict(list)
    for _ in range(n):
        w, v, g = map(int, input().split())
        groups[g].append((w, v))
        
    dp = [0] * (W + 1)
    
    # 遍历每一个组
    for group_id in groups:
        # 逆序遍历背包容量
        for j in range(W, -1, -1):
            # 遍历组内每一个物品，进行决策
            for w, v in groups[group_id]:
                if j >= w:
                    dp[j] = max(dp[j], dp[j - w] + v)
                    
    print(dp[W])

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 分组背包 (动态规划)
  • 时间复杂度: 。外层循环遍历所有组，内层循环遍历所有物品，总共是 个物品。对于每个物品，都需要更新 数组。因此总的循环次数约为 。
  • 空间复杂度: ，需要 的空间来存储分组后的物品，以及 的空间来存储 数组。