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

本文主要是介绍【算法 | 背包专题】01背包（状态定义+状态转移+解题流程+题单），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

什么是背包问题？

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

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

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

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

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

本节我们就来看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 * W)$ ，但是空间复杂度降低到了 $O (W)$ ，其中 $n$ 是物品的数量， $W$ 是背包的容量。

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

模板题 | 采药

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

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

题目描述

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

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

输入格式

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

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

输出格式

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

样例

样例输入

样例输出

提示

【数据范围】

对于 $30\%$ 的数据， $\le 10$ ；
对于全部的数据， $\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];}}

力扣题单

链接	题解
2915. 和为目标值的最长子序列的长度	题解
416. 分割等和子集	题解
494. 目标和	题解
2787. 将一个数字表示成幂的和的方案数	题解
1049. 最后一块石头的重量 II	题解

这篇关于【算法 | 背包专题】01背包（状态定义+状态转移+解题流程+题单）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！