背包问题是动静布局算法中十分经典的一类问题，也是口试面试中常见的一类问题。
背包问题有四类：0/1背包问题、齐全背包问题、多重背包问题、混合背包问题。
上面将总结0/1背包问题、齐全背包问题、多重背包问题三类问题。对于混合背包问题，难度较大，个别口试面试题也不会过多波及。
笔者自认为本文将背包问题总结地比拟全面，可不免有错漏，欢送批评指正！
一、0/1背包问题
1.1 经典0/1背包问题
你有一个背包，最多能包容的分量是m。当初有n个物品，第i个物品的分量为w[i] ,价值为v[i]。求这个背包至少能装多大价值的物品？
本例可参考：NC11 【模板】01背包
动静布局是一个将大问题划分为小问题进行解决，从而一步步获取最优解的过程。对于0/1背包问题，思考子问题“求解将前 i 个物品放入容量为 j 的背包中的最大价值”，设 F(i, j) 为将前 i 个物品放入容量为 j 的背包中最优解的总价值。对于第 i 个物品，事实上有两种状况：
- w[i] > j，即第 i 个物品的分量大于背包容量 j，则不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值，即 F[i][j] = F[i-1][j]。
w[i] ≤ j，即第 i 个物品的分量不大于背包容量 j，则有以下两种状况的最大值决定：
- 不放入该物品，此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值，即 F[i][j] = F[i-1][j]。
- 放入该物品，此时背包的残余容量为 j-w[i]，则最优解的值等同于“第 i 个物品的价值”与“前 i-1 个物品放入容量为 j-w[i] 的背包中最优解的值”之和，即F[i][j] = v[i] + F[i - 1][j - w[i]]。
（留神了解上述过程：是先比拟第i个物品的分量与背包容量，若能放，再比拟放入第i个物品与不放入第i个物品哪个能失去前i个物品状况下的最优解！）
因而能够失去递推公式：
$$初始条件：F(i,0) = F(0, j) = 0 \\$$
和
$$F(i,j)=\begin{cases}F(i-1, j), & w[i] > j \\max\{ F(i-1,j),v[i] + F(i - 1)(j - w[i]) \}, & w[i] ≤ j\end{cases}$$
给出如下一个例子：
背包的承重m = 5。当初有4个物品如下，求背包至少能装多大价值的物品：
物品 分量 价值 1 2 12 2 1 10 3 3 20 4 2 15
对于n=4, m=5的背包问题，应建设一个dp[n+1][m+1]的二维表。填表过程如下：
你是否对这个填表过程感到相熟？是的，所谓背包问题，其实还是后面的二维动静布局问题！
填表过程的代码如下：
/** * @param w 物品的分量 * @param v 物品的价值 * @param n 物品的个数 * @param m 背包的容量 */public static int knapsack1(int[] w, int[] v, int n, int m) { int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i < n + 1; i++) { for (int j = 1; j < m + 1; j++) { if (w[i - 1] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - w[i - 1]]); } } return dp[n][m];}看到这里，你可能会感到纳闷，为什么要这样填表？这样填写进去的表不是与这n件物品的存储程序无关吗？然而常识通知咱们，这个问题的解答不应该与物品程序相干呀？
是的，本问题的核心思想就是“求解将前 i 个物品放入容量为 j 的背包中的最大价值”，而不同的物品程序显然填进去的表是不雷同的。然而，这个动静规划表并不是咱们须要的后果，咱们也并不关怀”前 i 个物品放入容量为 j 的背包“的问题，咱们关怀的是“n 个物品放入容量为 m 的背包”的问题。尽管不同物品程序得出的动静规划表不一样，但其最优解的值肯定是一样的，而这才是咱们关怀的。
接下来将介绍如何回溯失去最优计划。
1.2 回溯、输入最优解
咱们先用图示的办法看看如何从动静规划表进行回溯、得出最优解的计划：
上述回溯过程仿佛很简单，然而在代码中能够退出一个辅助数组path[][]来记录更新的物品。则求出最优计划的代码如下：
public static void knapsack2(int[] w, int[] v, int n, int m) { int[][] dp = new int[n + 1][m + 1]; int[][] path = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (w[i - 1] > j) dp[i][j] = dp[i - 1][j]; else { if (dp[i - 1][j] < v[i - 1] + dp[i - 1][j - w[i - 1]]) { dp[i][j] = v[i - 1] + dp[i - 1][j - w[i - 1]]; path[i][j] = 1; } else { dp[i][j] = dp[i - 1][j]; } } } } for (int i = n, j = m; i >= 0; i--) { if (path[i][j] == 1) { System.out.println("放入第" + i + "个物品"); j = j - w[i - 1]; // 回溯过程体现在这里！ } } System.out.println("最大价值为: " + dp[n][m]);}上文提到，不同的物品程序失去的动静规划表不同，但最优解的值是雷同的。然而，雷同的只有最优解的值，因为最优解的计划是须要依据动静布局过程回溯失去的，因而最优解的计划却不肯定一样。
例如将上例中物品1的价值批改为10，求得的最优解尽管同样是35，却存在 {物品1, 物品2, 物品4} 和 {物品3, 物品4} 两个最优计划。你能够应用上面两个例子进行测试：
// 示例1int[] w = {2, 1, 3, 2}; // 物品的分量int[] v = {10, 10, 20, 15}; // 物品的价值int n = w.length; // 物品的个数int m = 5; // 背包的容量knapsack2(w, v, n, m);// 示例2int[] w = {3, 1, 2, 2}; // 物品的分量int[] v = {20, 10, 10, 15}; // 物品的价值int n = w.length; // 物品的个数int m = 5; // 背包的容量knapsack2(w, v, n, m);以上两个例子仅仅替换了物品的程序，尽管最优解的值雷同，但最优计划却不同。
那么，怎么判断最优解的计划是否惟一呢？在填表过程中，如果 F[i-1][j] 与 v[i] + F[i - 1][j - w[i]] 相等，则可阐明存在多个最优计划。
1.3 改良1：记忆性能
注：此办法不需把握，可间接跳过。然而看完之后，置信你会对动静布局有更深一步的理解。
动静布局算法是自底向上的：动静布局算法从最小的子问题登程，应用较小子问题的解去填充表格，每个子问题只解一次。然而，有些较小的子问题的解经常不是必须的。
递归的算法是自顶向下的：递归算法对递推式的求解将导致须要不止一次地解公共的子问题。例如斐波那契数列问题，递归算法将多次重复计算雷同值，因而效率非常低。
将自底向上的动静布局算法与自顶向下的递归算法联合起来，使它只对必要的子问题求解且只求解一次，这就是记忆性能的办法。该办法自顶向下地应用递归进行求解，但还需保护一个自底向上的动静布局表格：
public class MFKnapsackDemo { public static void main(String[] args) { int[] w = {2, 1, 3, 2}; // 物品的分量 int[] v = {12, 10, 20, 15}; // 物品的价值 int n = w.length; // 物品的数量 int m = 5; // 背包的容量 MFKnapsack mfKnapsack = new MFKnapsack(m, w, v); System.out.println("最大价值为: " + mfKnapsack.knapsack(n, m)); }}class MFKnapsack { static int n; // 物品的个数 static int m; // 背包的容量 static int[] w; // 物品的分量 static int[] v; // 物品的价值 static int[][] dp; // 动静规划表 /** * 将w[]、v[]、dp[][]作为全局变量 * 对于dp[][]，将第0行、第0列初始化为0，其余全副初始化为-1 */ public MFKnapsack(int m, int[] w, int[] v) { this.m = m; this.w = w; this.v = v; this.n = w.length; dp = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = -1; } } } public static int knapsack(int i, int j){ if (dp[i][j] < 0){ if (j < w[i-1]) dp[i][j] = knapsack(i-1, j); else dp[i][j] = Math.max(knapsack(i-1, j), v[i-1] + knapsack(i-1, j-w[i-1])); } return dp[i][j]; }}递归调用过程不便画出填表的过程，对于该例，其动静规划表dp[][]为：
比照一般动静布局算法计算出的表格来看，退出记忆性能后，算法将只对必要的子问题进行求解。
然而，退出记忆性能后，它的工夫效率与惯例的动静布局算法是统一的，退出记忆性能对性能的改良并不会超过一个常数因子。但如果一个值的计算无奈在常数工夫内实现，那么记忆性能对性能的改良可能会更显著。
1.4 改良2：空间优化
回到经典的01背包问题，咱们再看一看外围表达式：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j],v[i] + dp[i - 1][j - w[i]] \}, & w[i] ≤ j\end{cases}$$
能够看到，求解 dp[i][j] 时，其实只须要第 i-1 行的第 j 列或者第 j - w[i] 列的后果，其余行的后果是不须要的。所以咱们真正须要的只有 i-1 这一行，在对 i 遍历时，第 i 层能够主动滚动笼罩掉第 i-1 层。
那么咱们就能够进行空间优化，将其优化为一维数组：
$$dp[j]=\begin{cases}dp[j], & w[i] > j \\max\{ dp[j],v[i] + dp[j - w[i]] \}, & w[i] ≤ j\end{cases}$$
如果依照这个公式填表，会发现存在以下问题：
呈现这个问题的起因是：从左向右遍历会导致，后批改的左边的值须要用到先批改的右边的值。
那么如何解决呢？很简略，将其批改为从右向左遍历即可：
依据填表过程，能够失去01背包问题的空间优化算法：
public static int knapsack3(int[] w, int[] v, int n, int m) { int[] dp = new int[m + 1]; for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { //if (w[i - 1] > j) dp[j] = dp[j]; if (w[i - 1] <= j) dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]); } } return dp[m];}1.5 恰好装满问题
你有一个背包，最多能包容的分量是m。当初有n个物品，第i个物品的分量为w[i] ,价值为v[i]。若背包恰好装满，求至少能装多大价值的物品？如果无解请返回0。
本例可参考：NC11 【模板】01背包
若应用空间优化，则应初始化 dp[0] 为 0，其余初始化为Integer.MIN_VALUE。
最初若 dp[m] 为负数则阐明恰好装满，若为正数则阐明无解。
对于NC11 【模板】01背包，给出我的代码：
import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] v = new int[n]; int[] w = new int[n]; for (int i = 0; i < n; i++) { w[i] = sc.nextInt(); v[i] = sc.nextInt(); } int[] dp = new int[m + 1]; for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { if (w[i - 1] <= j) dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]); } } System.out.println(dp[m]); Arrays.fill(dp, Integer.MIN_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { if (w[i - 1] <= j) dp[j] = Math.max(dp[j], v[i - 1] + dp[j - w[i - 1]]); } } if (dp[m] < 0) dp[m] = 0; System.out.print(dp[m]); }}二、齐全背包问题
看到这里先问一下大家，为什么叫做0/1背包问题呢？因为在0/1背包问题中，对于所有的物品只有放与不放两种状况。而齐全背包问题就不一样了，在齐全背包问题中，每种物品都有有限件可用：
你有一个背包，最多能包容的分量是m。当初有n种物品，每种物品有任意多个，第i个物品的分量为w[i] ,价值为v[i]。求这个背包至少能装多大价值的物品？
本例可参考：NC12 【模板】齐全背包
2.1 经典齐全背包问题
咱们先看一看经典01背包问题的方程：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j],v[i] + dp[i - 1][j - w[i]] \}, & w[i] ≤ j\end{cases}$$
对于齐全背包问题，因为每种物品有任意多个，那么咱们能够再退出一层循环 k，k 代表第 i 种物品有 k 件。
则 v[i] 应批改为 k*v[i]，w[i] 应批改为 k*w[i]，且应答遍历的k*v[i]+dp[i-1][j-k*w[i]]取最大值，因而能够失去齐全背包问题的方程：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j], max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j\end{cases}$$
代码如下：
public static int CompleteKnapsack1(int[] w, int[] v, int n, int m) { int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (w[i - 1] > j) dp[i][j] = dp[i - 1][j]; else { for (int k = 1; k <= j / w[i - 1]; k++) { int temp = Math.max(dp[i - 1][j], k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]); dp[i][j] = Math.max(dp[i][j], temp); } } } } return dp[n][m];}然而这种算法的工夫复杂度将达到 O(n^3)，性能太差，因而须要进行工夫复杂度的优化。
2.2 改良1：工夫优化
察看齐全背包问题的方程：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j &①\\max\{ dp[i-1][j],max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j &②\end{cases}$$
咱们发现，当 k=0 时，有dp[i-1][j]与k*v[i]+dp[i-1][j-k*w[i]]相等，故以上方程能够合并为：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j &①\\max\{ k * v[i] + dp[i - 1][j - k * w[i]] \}, & 0 ≤ k ≤ \frac {j} {w[i]} &②\end{cases}$$
对于式子②，咱们晓得有以下两种状况，二者的最大值即为 dp[i][j]：
不放入第 i 种物品。则有：
$$dp[i][j] = dp[i-1][j]$$
放入第 i 种物品。那么应该放入几件呢？由遍历计算得出的最大值决定：
$$dp[i][j] = max\{ k * v[i] + f[i-1][j-k*w[i]] \} \tag{1 ≤ k ≤ j/w[i]}$$
- 用
k+1替换k，该式能够写为：
$$ \begin{aligned} dp[i][j] & = max\{ (k+1) * v[i] + f[i-1][j-(k+1)*w[i]] \} \\ & = max\{ k * v[i] + f[i-1][j-(k+1)*w[i]] \} +v[i]\\ & = max\{ k * v[i] + f[i-1][j-w[i]-k*w[i]] \} +v[i]\end{aligned}\\(0 ≤ k ≤ j/w[i])$$
- 对于上述③式，用
j-w[i]替换j，该式能够写为：
$$dp[i][j-w[i]]=max\{ k * v[i] + dp[i - 1][j-w[i] - k * w[i]] \} \\(0 ≤ k ≤ j/w[i])$$
察看以上两个式子，能够失去：
$$dp[i][j] = dp[i][j-w[i]] + v[i] \tag{w[i] ≤ j}$$
- 用
综合不放入的状况与放入的状况，两者应取最大值，因而式子②能够写为：
$$dp[i][j] = max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \} \tag{w[i] ≤ j}$$
综上，联合式子①与式子②，因而齐全背包问题的方程为：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j\\max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j\end{cases}$$
因而能够写出代码：
public static int CompleteKnapsack2(int[] w, int[] v, int n, int m) { int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (w[i - 1] > j) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - w[i - 1]] + v[i - 1]); } } return dp[n][m];}2.3 改良2：空间优化
察看齐全背包问题的方程：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j\\max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j\end{cases}$$
能够看到，求解 dp[i][j] 时，其实只须要第 i-1 行的第 j 列或者以后第 i 行曾经求过的第 j-w[i] 列的后果，其余行的后果是不须要的。
那么咱们就能够进行空间优化，将其优化为一维数组：
$$dp[j]=\begin{cases}dp[j], & w[i] > j \\max\{ dp[j],dp[j - w[i]] +v[i]\}, & w[i] ≤ j\end{cases}$$
与0/1背包问题的空间优化不同，因为咱们须要的第 i 行的第 j-w[i] 列在以后值 j 的左侧，因而咱们必须对 j 从左向右遍历能力取到该值。
因而，空间优化后的齐全背包问题的代码如下：
public static int CompleteKnapsack3(int[] w, int[] v, int n, int m) { int[] dp = new int[m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (w[i - 1] <= j) dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]); } } return dp[m];}2.4 工夫优化的思路转换
下面的工夫优化的的数学过程是不是让你感到很妙又很晕呢？那么咱们换一种思路。
咱们晓得，动静布局是一个将大问题划分为小问题进行解决，从而一步步获取最优解的过程。
咱们将 F[i][j] 示意为“将前 i 个物品放入容量为 j 的背包中的最大价值”，对于第 i 种物品，有两种状况：
- w[i] > j，即第 i 个物品的分量大于背包容量 j。则不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中最优解的值，即 F[i][j] = F[i-1][j]。
w[i] ≤ j，即第 i 个物品的分量不大于背包容量 j。则有以下两种状况的最大值决定：
- 不放入该物品。此时最优解的值等同于将前 i-1 个物品放入容量为 j 的背包中的最大价值，即 F[i][j] = F[i-1][j]。
- 放入该物品。先放入一个物品，此物品的价值为v[i]，此时背包的残余容量为 j-w[i]。那么剩下的j-w[i]应该怎么再放入物品 i 呢？该问题就等同于“将前 i 个物品放入容量为 j-w[i] 的背包中的最大价值”。因而，F[i][j] = v[i] + F[i][j-w[i]]。
因而能够失去递推公式：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j\\max\{ dp[i-1][j], dp[i][j-w[i]] + v[i] \}, & w[i] ≤ j\end{cases}$$
怎么样？是不是更好了解了呢？
2.5 恰好装满问题
你有一个背包，最多能包容的分量是m。当初有n种物品，每种物品有任意多个，第i个物品的分量为w[i] ,价值为v[i]。若背包恰好装满，求至少能装多大价值的物品？如果无解请返回0。
本例可参考：NC12 【模板】齐全背包
若应用空间优化，则应初始化 dp[0] 为 0，其余初始化为Integer.MIN_VALUE。
最初若 dp[m] 为负数则阐明恰好装满，若为正数则阐明无解。
对于NC12 【模板】齐全背包，给出我的代码：
import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] v = new int[n]; int[] w = new int[n]; for (int i = 0; i < n; i++) { w[i] = sc.nextInt(); v[i] = sc.nextInt(); } int[] dp = new int[m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (j >= w[i - 1]) dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]); } } System.out.println(dp[m]); Arrays.fill(dp, Integer.MIN_VALUE); dp[0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (j >= w[i - 1]) dp[j] = Math.max(dp[j], dp[j - w[i - 1]] + v[i - 1]); } } if (dp[m] < 0) dp[m] = 0; System.out.print(dp[m]); }}三、多重背包问题
你有一个背包，最多能包容的分量是m。当初有n种物品，第i个物品的分量为w[i] ,价值为v[i]，数量为c[i]。求这个背包至少能装多大价值的物品？
本例可参考：多重背包
3.1 经典多重背包问题
咱们先察看齐全背包问题的方程：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j], max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j\end{cases}$$
那么，多重背包与齐全背包的区别在哪里呢？多重背包仅仅是对物品的数量多了个限度k≤c[i]：
$$dp[i][j]=\begin{cases}dp[i-1][j], & w[i] > j \\max\{ dp[i-1][j], max\{k * v[i] + dp[i - 1][j - k * w[i]]\} \}, & w[i] ≤ k * w[i] ≤ j & and & k ≤ c[i]\end{cases}$$
所以，仅仅须要对 k 循环的条件作批改即可。代码如下：
public static int MultipleKnapsack1(int[] w, int[] v, int[] c, int n, int m) { int[][] dp = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (w[i - 1] > j) dp[i][j] = dp[i - 1][j]; else { for (int k = 1; k <= j / w[i - 1] && k <= c[i - 1]; k++) { //比照齐全背包，仅需批改此处 int temp = Math.max(dp[i - 1][j], k * v[i - 1] + dp[i - 1][j - k * w[i - 1]]); dp[i][j] = Math.max(dp[i][j], temp); } } } } return dp[n][m];}3.2 改良1：空间优化
同样的，多重背包问题能够进行空间优化，其思路与0/1背包问题统一，须要思考到：若从左向右遍历，会导致后批改的左边的值须要用到先批改的右边的值。
因而，多重背包问题的 j 值须要从右向左遍历：
public static int MultipleKnapsack2(int[] w, int[] v, int[] c, int n, int m) { int[] dp2 = new int[m + 1]; for (int i = 1; i <= n; i++) { for (int j = m; j >= 1; j--) { if (w[i - 1] <= j) { for (int k = 1; k <= j / w[i - 1] && k <= c[i - 1]; k++) { dp2[j] = Math.max(dp2[j], k * v[i - 1] + dp2[j - k * w[i - 1]]); } } } } return dp[m];}3.3 改良2：二进制优化、枯燥队列优化
多重背包问题还能够进行二进制优化、枯燥队列优化。但笔者满腹经纶，就不多作介绍了。
OJ地址：多重背包的二进制优化、多重背包的枯燥队列优化
参考资料
- 【尚硅谷】Java数据结构与算法
- 清华大学出版社《算法设计与剖析根底（第3版）》Anany Levitin 著 潘彦 译
- 背包问题-笔记整顿