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

前言

什么是背包问题？

背包问题是一种经典的组合优化问题，它的核心思想是在有限的资源（如背包的容量）下，如何选择物品以达到某种目标（如最大价值）的最优解。

背包问题可以分为几种类型，其中最常见的有：

1. 0/1背包问题：每个物品只能选择放入或不放入背包，不能分割。
2. 完全背包问题：每种物品可以选择无限个，但每件物品只能选择一次。
3. 多重背包问题：每种物品可以选择多个，且没有数量限制。

解决方法也有很多，比如动态规划，回溯搜索、分支限界，贪心等。

背包问题在实际生活中有很多应用，如资源分配、项目投资组合、货物装载、课程安排等。通过解决背包问题，我们可以在有限的资源下做出最优的决策。

本节我们就来看01背包问题。

问题描述

01背包问题的描述如下：

• 现在，我们有一个背包，它有一个固定的承载重量限制 W（背包容量有限）。
• 同时，我们有一组物品，每个物品都有自己的重量weight[i]和价值value[i]。
• 我们需要从这组物品中选择一些物品放入背包，并且每件物品只能用一次
• 问：在不超过背包承载重量的前提下，放入背包的物品总价值最大是多少？

在01背包中，每个物品最多只能用一次。

问题求解

暴力

在这个经典的 01背包问题中，对于我们的决策，每一件物品只有两个状态：

• 选
• 不选

使用回溯法，我们可以搜索出所有情况，但时间复杂度是 $O(2^n)$（$n$表示物品数量），因此暴力的解法是通不过的，需要进一步优化。

对于01背包问题，最常用的求解方法是动态规划。

dp表的含义

使用动态规划的解法，需要定义状态（明确dp表的含义）和状态转移方程，将问题分解为子问题，然后通过迭代的方式，从小问题开始，逐步解决大问题。

我们来看，在01背包问题中，状态是如何定义的：

• dp[i][j]：在前i个物品中选取若干个，使得总重量不超过j的情况下，能够获得的最大价值。

明确好dp表的含义后，我们就可以进行状态转移的讨论以及编码。

状态转移

对于每个物品i以及当前的背包容量j，我们考虑两种情况（选或不选）：

• 如果不选取第i个物品：
  • 那么背包中物品的总价值就是在前i-1个物品中选取若干个，使得总重量不超过j的情况下，能够获得的最大价值，
  • 即dp[i][j] = dp[i - 1][j]。
• 如果选取第i个物品：
  • 背包中物品的总价值就是在前i-1个物品中选取若干个，使得总重量不超过j-weight[i]的情况下，能够获得的最大价值，再加上第i个物品的价值，
  • 即dp[i][j] = dp[i - 1][j - weight[i]] + value[i]。

我们对每个物品的每种可能性进行考虑，从而找出在总重量不超过背包容量的前提下，能够获得的最大价值。这就是01背包问题的解题思路。

解题流程

定义好状态，以及转移方程后，我们就可以开始推了。从第1个物品开始，对于每个物品，遍历所有的背包容量，根据状态转移方程更新dp表。最后，dp[n][t]就是最大价值。

在使用动态规划时，初始化操作是很关键的一步。对于dp[0][j]（没有物品时），无论背包容量是多少，最大价值都是0，因此初始化就都是0。

代码如下：

/**
 * 使用动态规划解决01背包问题
 * @param weight 物品的重量数组
 * @param value 物品的价值数组
 * @param W 背包的总容量
 * @return 能够获得的最大价值
 */
public static int compute(int[] weight, int[] value, int W) {
    int n = value.length;	// 有n件物品
    
    // dp[i][j]表示在前i个物品中选取若干个，使得总重量不超过j的情况下，能够获得的最大价值
    int[][] dp = new int[n+1][W+1];
    
    // 遍历每一个物品
    for(int i = 1; i<=n; i++) {
        // 遍历每一种背包容量
        for(int j = 0; j<=W; j++) {
            // 不选取第i个物品
            dp[i][j] = dp[i-1][j];
            // 如果背包的剩余容量大于等于当前物品的重量，考虑选取第i个物品
            if(j >= weight[i]) {
                // 选取第i个物品，更新最大价值
                dp[i][j] = Math.max(dp[i][j], dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }
     
    // 返回在前n个物品中选取若干个，使得总重量不超过W的情况下，能够获得的最大价值
    return dp[n][W];
}

空间压缩

在上述代码中，我们可以看到，每次更新dp[i][j]时，我们只用到了上一行的数据，即dp[i-1][j]和dp[i-1][j-weight[i]]。这意味着我们并不需要保存所有的dp[i][j]，只需要保存上一行的数据就足够了，因此，我们可以将二维dp表改进为一维，俗称空间压缩。

空间压缩的思路是，我们使用一个一维数组dp[j]来代替二维数组dp[i][j]。dp[j]表示在当前考虑的物品中选取若干个，使得总重量不超过j的情况下，能够获得的最大价值。

需要注意的是，我们每次在更新dp[i][j]时，总是用到了上一行中的dp[i-1][j]和dp[i-1][j-weight[i]]，在二维表中可以形象理解为，我所处的位置，依赖于上方的格子，以及左上方的格子。因此，进行空间压缩更新dp[j]时，我们需要从后往前更新dp[j]，这样可以逐渐更新当前的格子。

如果我们从前往后更新，那么在计算dp[j]时，dp[j-weights[i]]可能已经被更新过了，它表示的是当前行的状态，而不是上一行的状态。而我们需要的是上一行的状态，因此我们必须从后往前更新。

下面是空间压缩后的代码：

/**
 * 使用动态规划解决01背包问题（空间压缩版本）
 * @param weight 物品的重量数组
 * @param value 物品的价值数组
 * @param W 背包的总容量
 * @return 能够获得的最大价值
 */
public static int compute(int[] weight, int[] value, int W) {
    int n = value.length;	// 有n件物品
    
    // dp[j]表示在当前考虑的物品中选取若干个，使得总重量不超过j的情况下，能够获得的最大价值
    int[] dp = new int[W+1];
    
    // 遍历每一个物品
    for(int i = 1; i<=n; i++) {
        // 从后往前更新dp[j]
        for(int j = W; j>=weight[i]; j--) {
            // 选取第i个物品，更新最大价值
            dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
        }
    }
     
    // 返回在所有物品中选取若干个，使得总重量不超过W的情况下，能够获得的最大价值
    return dp[W];
}

这段代码的时间复杂度仍然是$O(n\ast W)$，但是空间复杂度降低到了$O(W)$，其中$n$是物品的数量，$W$是背包的容量。

注意，我们后面会经常使用空间压缩的版本，因此需要吃透这份代码。

模板题 | 采药

我们来看一道洛谷上的模板题。

测试链接：P1048 [NOIP2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$（$1\le T\le 1000$）和 $M$（$1\le M\le 100$），用一个空格隔开，$T$ 代表总共能够用来采药的时间，$M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例

样例输入

70 3
71 100
69 1
1 2

样例输出

3

提示

【数据范围】

• 对于 $30\%$ 的数据，$M\le 10$；
• 对于全部的数据，$M\le 100$。

【题目来源】

NOIP 2005 普及组第三题

解题

这道题就是标准的01背包问题，每种草药只能采摘一次，也就是说每种物品只能选择一次或者不选择，不能选择多次。

我们定义dp[i][j]为在前i种草药中选取若干种，使得总时间不超过j的情况下，能够获得的最大价值。对于第i种草药，我们可以选择采摘，也可以选择不采摘。如果我们选择采摘，那么我们需要在剩余的时间j-weight[i]中选择前i-1种草药，使得总价值最大；如果我们选择不采摘，那么我们需要在时间j中选择前i-1种草药，使得总价值最大。

我们取这两种情况的最大值，就是dp[i][j]的值。

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

public class Main {

	static int N = 101; // 草药的最大数量

	static int W = 1001;// 总时间的最大值

	static int[] weight = new int[N]; // 每种草药的采摘时间

	static int[] value = new int[N]; // 每种草药的采摘价值

	static int n, w; // 分别表示草药的数量和总时间

	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) {
			w = (int) in.nval;
			in.nextToken();
			n = (int) in.nval;
			for (int i = 1; i <= n; i++) {
				in.nextToken();
				weight[i] = (int) in.nval;
				in.nextToken();
				value[i] = (int) in.nval;
			}
			out.println(compute2());
		}
		out.flush();
		out.close();
		br.close();
	}

	// 经典解法
	public static int compute1() {
		// dp[i][j]表示在前i个草药中选取若干个，使得总时间不超过j的情况下，能够获得的最大价值
		int[][] dp = new int[n + 1][w + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= w; j++) {
				// 不要i号草药
				dp[i][j] = dp[i - 1][j];
				if (j - weight[i] >= 0) {
					// 要i号草药
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - weight[i]] + value[i]);
				}
			}
		}
		return dp[n][w];
	}

	// 空间压缩版本
	public static int compute2() { 
		int[] dp = new int[w + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = w; j >= weight[i]; j--) {
				dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}
		return dp[w];
	}

}

力扣题单