【算法 | 背包专题】分组背包（解题思路+题单）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法 | 背包专题】分组背包（解题思路+题单）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

分组背包

上一节，我们提到了什么是01背包，以及如何求解01背包：

【算法 | 背包专题】01背包（状态定义+状态转移+解题流程+题单）

现在，我们来看分组背包。

分组背包问题是背包问题的一种变形。在这个问题中，物品被分成了若干组，每组中的物品相互冲突，也就是说，每组只能选择一个物品。这与01背包问题的主要区别在于，01背包问题中，每个物品都可以被选择，而在分组背包问题中，每组只能选择一个物品。

求解分组背包问题的基本思路是动态规划。我们可以定义一个二维数组dp[i][j]，表示前i组物品，总重量不超过j的情况下的最大价值。然后，我们可以遍历每一组物品，对于每一组中的每一个物品，我们都尝试将其加入背包，更新dp[i][j]的值。

欸，这就是分组背包的求解思路，每一组物品都进行可能性展开，去尝试。

模板题

我们来看这道模板题。

通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m, n$ ，表示一共有 $n$ 件物品，总重量为 $m$ 。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$ ，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例

样例输入

样例输出

提示

$\leq m \leq 1000$ ， $\leq n \leq 1000$ ， $1\leq k\leq 100$ ， $a_i, b_i, c_i$ 在 int 范围内。

状态定义

对于这道题（分组背包问题），我们使用动态规划来解决，定义一个二维数组 dp[i][j]，表示前i组物品，总重量不超过j的情况下的最大价值。

解题思路

首先获取背包的总重量m和物品的数量n，然后读取每个物品的重量、价值和所属组号，接着，将物品按照组号进行排序（重要）。
接下来，我们计算出总共有多少个组（用变量group存储起来）。
初始化dp数组，dp[0][j] = 0，表示没有物品的情况下，任何重量的背包获取的价值都是0（在Java中默认值都是0）。
遍历每一组物品。对于每一组，我们都尝试将组内的每一个物品加入背包，更新dp[i][j]的值。具体来说，如果物品的重量小于或等于j，那么我们可以选择将其加入背包，此时dp[i][j] = max(dp[i-1][j], dp[i-1][j-物品的重量] + 物品的价值)。
最后，dp[group][m]就是我们要求的答案，表示前group组物品，总重量不超过m的情况下获取的最大价值。

参考代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

    public static int MAXN = 1001;

    public static int MAXM = 1001;

    public static int[][] arr = new int[MAXN][3]; // (体积, 价值, 所属组号)

    public static int n, m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            m = (int) in.nval;
            in.nextToken();
            n = (int) in.nval;
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                arr[i][0] = (int) in.nval; // 体积
                in.nextToken();
                arr[i][1] = (int) in.nval; // 价值
                in.nextToken();
                arr[i][2] = (int) in.nval; // 所属组号
            }
            // 将物品按照组号进行排序
            Arrays.sort(arr, 1, n + 1, (a, b) -> a[2] - b[2]);
            // 输出计算结果
            out.println(compute());
        }
        out.flush();
        out.close();
        br.close();
    }

    // dp[i][j]: 前i组里面，每组最多挑选一件，在容量不超过j的情况下，最大价值是多少？
    public static int compute() {
    	// 首先我们计算总共有多少个组，编号从1开始
        int group = 1;
        for (int i = 2; i <= n; i++) {
            if (arr[i - 1][2] != arr[i][2]) {
                group++;
            }
        }
        int[][] dp = new int[group + 1][m + 1];
        
        for (int start = 1, end = 2, i = 1; start <= n; i++) {
        	// 第i组的范围是 [start, end)，注意，范围是左闭右开的
            while (end <= n && arr[end][2] == arr[start][2]) {
                end++;
            }
            // 当知晓第i组的范围之后，就可以进行动态规划了
            for (int j = 0; j <= m; j++) { // 遍历背包容量
            	// 不选物品
                dp[i][j] = dp[i - 1][j];
                // 每一件物品都试一遍，k指的是物品编号
                for (int k = start; k < end; k++) {
                	// 如果背包容量允许，则尝试
                    if (j >= arr[k][0]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[k][0]] + arr[k][1]);
                    }
                }
            }
            // 要记得更新 start !!!
            start = end++;
        }
        // 最后返回前group组里面，每组最多挑选一件，在容量不超过j的情况下，最大价值是多少？
        return dp[group][m];
    }
}

空间压缩

和 01 背包一样，我们也要对分组背包进行空间压缩，优化空间复杂度。

我们可以观察到，dp[i][j]的值只依赖于dp[i-1][j]和dp[i-1][j-arr[k][0]]，也就是说，计算dp[i][j]的值时，只需要知道第i-1组的信息，而不需要知道i-2、i-3等更早的组的信息。因此，我们可以只用一个一维数组dp[j]来存储每一组的信息，当我们处理完一组物品后，就可以覆盖掉这一组的信息，用来存储下一组的信息。

另外，在遍历所有可能的背包容量，以便计算出每种容量下的最大价值时，我们要注意遍历的顺序（即从后往前遍历）。

这是因为我们是在原地更新dp数组，如果我们从前往后遍历背包容量，那么在计算dp[j]时，dp[j - arr[k][0]]可能已经被更新过了，这就导致我们使用的是错误的值。为了避免这个问题，我们需要从后往前遍历背包容量。这样，在计算dp[j]时，dp[j - arr[k][0]]还没有被更新，我们可以安全地使用它的值。

参考代码如下：

// dp[i]: 每组商品最多挑选一件，在容量不超过i的情况下，最大价值是多少？
public static int compute() {
	int[] dp = new int[m + 1];
	// 同样，第i组的范围是 [start, end)，注意，范围是左闭右开的
	int start = 1, end = 2;
	while (start <= n) {
		// 首先，找到当前组的范围
		while (end <= n && arr[end][2] == arr[start][2]) {
			end++;
		}
		// 知道当前组的范围后，就可以开始动态规划了，注意背包容量需要从后往前遍历
		// 因为从前往后遍历的话，会覆盖掉之前的数据，进而影响到后续元素的遍历
		for (int j = m; j >= 0; j--) {
			for (int k = start; k < end; k++) {
				if (j >= arr[k][0]) {
					dp[j] = Math.max(dp[j], dp[j - arr[k][0]] + arr[k][1]);
				}
			}
		}
		// 不要忘了更新 start
		start = end++;
	}
	return dp[m];
}

力扣题单

学完后，我们可以刷几道力扣题巩固一下。文章来源地址https://www.toymoban.com/news/detail-847146.html

题目	题解
1155. 掷骰子等于目标和的方法数	题解
1981. 最小化目标值与所选元素的差	题解
2218. 从栈中取出 K 个硬币的最大面值和	题解