你真的懂01背包问题吗？01背包的这几问你能答出来吗？
对于01背包的几个问题
- 背包问题的动静转移方程是怎么来的？
- 你能解释背包问题的两个
for循环的意义嘛？ - 为什么须要两个
for循环，一个循环行不行？ - 01背包问题的
for循环肯定要从0开始吗？ - 01背包滚动数组的优化原理是什么？
- 01背包只用不必二维数组只用一位数组的根据是什么？
这些问题在浏览完本文之后你将会失去答案！
01背包问题介绍
有 $N$件物品和一个容量是 $V$ 的背包。每件物品只能应用一次。第$i$件物品的体积是$v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。比方上面的4个物品，背包可能接受的最大分量为5，咱们应该如何抉择，使得咱们取得的总价值最大：
| 物品 | 分量 | 价值 |
|---|---|---|
| A | 1 | 2 |
| B | 2 | 4 |
| C | 3 | 4 |
| D | 4 | 5 |
这个问题还是比较简单，咱们间接看就晓得抉择物品B和物品C失去的价值最大。那么咱们如何设计一个算法去实现这个问题呢？首先对于每一个物品都有两种状况，抉择和不抉择，咱们须要抉择两种状况当中可能获取最大价值的那种状况。
01背包问题动静转移方程
首先我么先要确定一个信息就是没件物品只有一件，选完就没有了。如果咱们的背包当中还有残余容量能够放下某个物品，那么对于这个物品咱们就有两种抉择：选或者不选。
咱们定义数组dp[i][j]，其含意是对于前i件物品，在咱们的背包容量为j的状况下咱们可能取得的最大的收益，如果咱们有N件物品，背包容量为V，那么咱们可能取得的最大价值为dp[N][V]，因为他示意的是对于前N个物品，在背包容量为V的状况下咱们可能获取到的最大的价值。咱们能够失去上面的公式：
$$dp[i][j]=max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])，如果背包的容量大于等于物品 i 占的体积$$
$$dp[i][j]=dp[i - 1][j]，如果背包的容量小于物品 i 占的体积$$
第一种状况（背包容量大于等于第
i件物品的体积v[i]时）：- 在这种状况下咱们对于第
i件物品有两种抉择，一种是将其放入背包当中，另外一种就是不选他，那么咱们就能够应用容量为j的背包在前i-1件物品进行抉择。 - 如果咱们选第
i件物品，那么咱们背包剩下的容量就为j - v[i]，咱们还能抉择的物品就是前i - 1个物品，这个状况下可能取得的最大的收益为$dp[i - 1][j - v[i]]$，再加上咱们抉择的第i件物品的价值，咱们抉择第i件物品可能取得的总收益为dp[i - 1][j - v[i]] + w[i]。 - 如果咱们不抉择第
i件物品，那么咱们背包残余容量依然为j，而且咱们只能从前i - 1个商品当中进行抉择，那么咱们最大的收益就为dp[i - 1][j]。
- 在这种状况下咱们对于第
第二种状况（背包容量小于第
i件物品的体积v[i]时）：- 这种状况下咱们只可能抉择前
i - 1个商品，因而咱们可能获取的最大收益为dp[i - 1][j]。
- 这种状况下咱们只可能抉择前
01背包数据依赖问题剖析
在上文当中咱们曾经剖析进去了咱们的动静转移方程：
$$dp[i][j]=max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])，如果背包的容量大于等于物品 i 占的体积$$
$$dp[i][j]=dp[i - 1][j]，如果背包的容量小于物品 i 占的体积$$
依据下面两个公式剖析，咱们晓得要想解出dp[i][j]的值，咱们首先须要晓得dp[i - 1][j - v[i]]的值和dp[i - 1][j]的值，他们之间的依赖关系如下图所示：
基于下面的数据依赖关系，咱们晓得咱们如果想求dp[N][V]的值，首先要求出dp数组第N - 1行的所有的值，因为dp[N][V]依赖dp[N - 1][V]，而且可能依赖dp[N - 1][i]的值（i大于等于0，小于V），而dp[N - 1][V]又依赖dp[N - 2][]V......
依据下面的剖析过程，如果咱们想计算出dp[N][V]的后果，那就须要从第1行开始往后计算，始终算到第N行，因而咱们能够写出上面的代码：
Java版本：
import java.util.Scanner;public class Main { public static int backpack(int[] w, int[] v, int N, int V) { int[][] dp = new int[N + 1][V + 1]; // 初始化 for (int i = v[1]; i <= V; ++i) { dp[1][i] = w[1]; } // 第一行曾经初始化 从第二行开始 for (int i = 2; i <= N; ++i) { for (int j = 0; j <= V; ++j) { if (j >= v[i]) dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]); else dp[i][j] = dp[i - 1][j]; } } return dp[N][V]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); int[] w = new int[N + 1]; int[] v = new int[N + 1]; for (int i = 1; i <= N; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } System.out.println(backpack(w, v, N, V)); }}C++版本：
#include <iostream>using namespace std;#define L 20000int w[L]; // 物品价值int v[L]; // 物品体积int dp[L][L];int N; // 物品数量int V; // 背包的体积int backpack() { // 初始化 for (int i = v[1]; i <= V; ++i) { dp[1][i] = w[1]; } // 第一行曾经初始化 从第二行开始 for (int i = 2; i <= N; ++i) { for (int j = 0; j <= V; ++j) { if (j >= v[i]) dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]); else dp[i][j] = dp[i - 1][j]; } } return dp[N][V];}int main() { cin >> N >> V; for (int i = 1; i <= N; ++i) { cin >> v[i] >> w[i]; } cout << backpack(); return 0;}从上图看咱们在计算第i的数据的时候咱们只依赖第i - 1行，咱们在第i行从后往前遍历并不会毁坏动静转移公式的要求。
因而上面的代码也是正确的：
public static int backpack(int[] w, int[] v, int N, int V) { int[][] dp = new int[N + 1][V + 1]; // 初始化 for (int i = v[1]; i <= V; ++i) { dp[1][i] = w[1]; } // 第一行曾经初始化 从第二行开始 for (int i = 2; i <= N; ++i) { // 这里是从开端到0 // 后面是从0遍历到开端 for (int j = V; j >= 0; --j) { if (j >= v[i]) dp[i][j] = Math.max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]); else dp[i][j] = dp[i - 1][j]; } } return dp[N][V];}01背包问题优化——滚动数组
咱们在解决背包问的时候咱们是开拓了一个二维数组dp，那么咱们能不能想斐波拉契数列那样升高算法的空间复杂度呢？咱们曾经很分明了咱们在计算dp数据的时候进行计算的时候只应用了两行数据，那么咱们只须要申请两行的空间即可，不须要申请那么大的数组空间，计算的时候重复在两行数据当中交替计算既可。比如说咱们曾经计算好第一行的数据了（初始化），那么咱们能够依据第一行失去的后果失去第二行，而后依据第二行，将计算的结后果从新存储到第一行，如此交替重复，像这种办法叫做滚动数组。
上面的代码当中dp数组是从第0行开始应用的，后面的代码是从第一行开始的。
import java.util.Scanner;public class Main { public static int backpack(int[] v, int[] w, int V) { int N = w.length; int[][] dp = new int[2][V + 1]; for (int i = v[0]; i < V; ++i) { dp[0][i] = w[0]; } for (int i = 1; i < N; ++i) { for (int j = V; j >= 0; --j) { if (j >= v[i]) dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - v[i]] + w[i]); else dp[i % 2][j] = dp[(i - 1) % 2][j]; } } return dp[(N - 1) % 2][V]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); int[] w = new int[N]; int[] v = new int[N]; for (int i = 0; i < N; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } System.out.println(backpack(v, w, V)); }}背包空间再优化——单行数组和它的遍历程序问题
咱们还能持续压缩空间吗？咱们在进行空间问题的优化的时候只有不毁坏动静转移公式，只须要咱们进行的优化可能满足dp[i][j]的计算在它所依赖的数据之后计算即可。
import java.util.Scanner;public class Main { public static int backpack(int[] v, int[] w, int V) { int N = w.length; int[] dp = new int[V + 1]; for (int i = v[0]; i < V; ++i) { dp[i] = w[0]; } for (int i = 1; i < N; ++i) { for (int j = V; j >= v[i]; --j) { dp[j] = Math.max(dp[j - v[i]] + w[i], dp[j]); } } return dp[V]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int V = scanner.nextInt(); int[] w = new int[N]; int[] v = new int[N]; for (int i = 0; i < N; i++) { v[i] = scanner.nextInt(); w[i] = scanner.nextInt(); } System.out.println(backpack(v, w, V)); }}咱们当初来好好剖析一下下面的代码：
- 依据动静转移公式
dp[i][j] = max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])咱们晓得，第i行的第j个数据只依赖第i - 1行的前j个数据，跟第j个数据之后的数据没有关系。因而咱们在应用一维数组的时候能够从后往前计算（且只能从后往前计算，如果从前往后计算会毁坏动静转移公式，因为第j个数据跟他后面的数据有依赖关系，跟他前面的数据没有依赖关系）就可能满足咱们的动静转移公式。
- 如果咱们从在应用单行数组的时候从前往后计算，那么会使得一维数据后面局部数据的状态从
i - 1行的状态变成第i行的状态，像上面这样。
然而一维数组当中后局部的数据还是i - 1行的状态，当咱们去更新他们的时候他们依赖后面局部数据的i - 1行的状态，然而他们曾经更新到第i的状态了，因而毁坏了动静布局的转移方程，然而如果咱们从后往前进行遍历那么后面的状态始终是第i - 1行的状态，因而没有毁坏动静布局的转移方程，因而咱们须要从后往前遍历。
问题答案
如果你曾经看懂下面所议论到的内容的话，对于后面的几个问题置信你曾经有了答案。下面那些问题最终波及到的就是01背包问题的动静转移方程了，咱们在写代码的时候肯定不能毁坏动静转移方程，也就是要满足动静转移方程的依赖关系，即第i行的第j个数据只依赖第i - 1行的前j个数据，跟第j个数据之后的数据没有关系。
背包问题的两个
for循环的意义：- 因为咱们须要解出
dp数组当中第N行第V列的数据，所以咱们须要解出二维数组当中所有的数据，因而咱们须要进行二维数组的遍历，进行一维遍历不行。
- 因为咱们须要解出
01背包问题的
for循环肯定要从0开始吗？- 不肯定，咱们只须要满足动静转移方程的数据依赖要求就行，不论是从返回后还是从后往前咱们在应用二维
dp数组的遍历的时候都能够满足数据依赖的要求。然而咱们如果应用一维数组的时候就肯定要从后往前遍历，因为如果从前往后遍历，第i行状态会笼罩第i - 1行的状态，而数组前面的数据须要i - 1行状态的数据，而它有被笼罩了因而不行。
- 不肯定，咱们只须要满足动静转移方程的数据依赖要求就行，不论是从返回后还是从后往前咱们在应用二维
- 其余问题的答案在浏览完本文之后置信你心里曾经很分明了！！！
动静布局为什么叫动静布局
首先咱们须要明确什么是布局所谓的布局 就是寻找最优值的过程，比如说咱们在旅行的时候做布局就是为了又更好旅行体验，而咱们在做算法题的时候须要找到最好的后果，比方在背包问题当中咱们要找到价值最大的一种抉择，这也是一种布局，那为什么是动静的呢？所谓动静就是咱们在寻找最优值的过程当中，抉择是变动的。比如说对于背包问题的公式dp[i][j] = max(dp[i - 1][j - v[i] + w[i], dp[i - 1][j])咱们在计算出后果之前并不知道那种抉择好，因为咱们要抉择两者两头值较大的哪个抉择，这就是动静抉择的过程！所以动静布局被称作动静布局！
总结
本篇文章次要带大家从0开始分析01背包问题，次要分享一些根本但常常被疏忽的问题，比方二重循环是如何被写进去的，for循环的程序问题，数组空间优化问题的原理，用一维数组解决01背包问题！心愿大家有所播种，我是LeHung，咱们下期再见！！！
更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu...
关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。