0/1背包问题（动态规划+动规优化）

题目地址

大致描述就是有 N 个物品&＃xff0c;每件物品有各自的重量 W 及价值 V&＃xff0c;有一个最大容量为 C 的背包&＃xff0c;求在不超过这个背包的容量下能装入物品的最大价值。&＃xff08;N&＃xff0c;W&＃xff0c;V&＃xff0c;C都为整数&＃xff09;

假如对这些物品从1~i 进行编号&＃xff0c;并用两个数组V、W分别保存物品的价值和重量&＃xff0c;相应的 V[ i ] 和 W[ i ] 表示的意义是第 i 件物品的价值和重量。

首先定义F[ i ][ j ] &＃61; 在背包容量为 j 的情况下从前 i 件物品中能选取到的最大价值。这个定义的理解非常重要&＃xff0c;它表示的是不同限制情况下的最优解。注意此处的 j 并不是题中描述的最大容量C&＃xff0c;而是可以取从0~C的所有整数。

那么根据这个定义可以得到状态转移方程&＃xff1a;F[ i ] [ j ] &＃61; max( F[ i-1 ] [ j ]&＃xff0c;F[ i-1 ] [ j-W[ i ] ] &＃43; V[ i ])

这个方程表示的意义是&＃xff0c;在背包容量 j 的情况下对于物品 i &＃xff1a;

• 如果W[ i ]>j&＃xff0c;物品重量超出背包容量肯定不能选&＃xff0c;那么从前 i 个物品中装入等价于从前 i-1 个物品中装入&＃xff0c;
  对应的状态转移方程 F[ i ] [ j ] &＃61; F[ i-1 ] [ j ] 。
• 如果W[ i ]≤j&＃xff0c;假设选入&＃xff0c;注意这里是假设&＃xff0c;那么有 F[ i ] [ j ] &＃61; F[ i-1 ] [ j-W[ i ] ] &＃43; V[ i ] &＃xff0c;也就是在背包总容量减去物品 i 重量后的基础上&＃xff0c;前 i-1 件物品中的最优解&＃43;物品 i 的价值。

注意上面的 j 均表示的是背包总容量&＃xff0c;而不是减去某物品重量后剩余的。

现在回到大方程 F[ i ] [ j ] &＃61; max( F[ i-1 ] [ j ]&＃xff0c;F[ i-1 ] [ j-W[ i ] ] &＃43; V[ i ])&＃xff0c;它是在上面两种情况下取最大值&＃xff0c;这也是为什么上面强调假设的原因&＃xff0c;它表明的意义是即使物品 i 重量不大于背包总容量&＃xff0c;也并不一定是非选它不可&＃xff0c; 具体还要看能不能从前 i-1 件中选出更大的价值。

从大方程可以看出&＃xff0c;背包容量 j 下前 i 件物品中的最优解&＃xff0c;只和背包容量 j 下前 i-1 件物品中的最优解和背包容量减去物品 i 重量下前 i-1 件物品中的最优解有关。因此&＃xff0c;可以通过循环迭代将不同情况限制下的最优解填写成一张表&＃xff0c;类似下图&＃xff0c;并可以根据这张表直接得到不同限制情况下的最优解。

物品编号和背包容量都含0是为了编程方便&＃xff0c;并根据表示的实际意义&＃xff0c;物品编号为0或背包容量为0时的最大价值应该设为0。

同样下面代码中W&＃xff0c;V数组传入时也要将第一位先设为0。比如上图对应的W数组&＃xff1a;{0,7,5,4,8,12}&＃xff0c;V数组&＃xff1a;{0,13,8,20,11,6}&＃xff0c;但这里设0只是起到了占位的作用&＃xff0c;也可以设为其它数字。

public class Knapsack_01 {public static int knapsack(int[] W, int[] V, int C) {// 创建二维数组用来保存不同限制条件下的最优解// 注意dp[0][],dp[][0]虽然没有显式初始化0但由于是int数组,默认都为0int[][] dp &＃61; new int[W.length][C &＃43; 1];for (int i &＃61; 1; i < W.length; i&＃43;&＃43;) {for (int j &＃61; 1; j < C &＃43; 1; j&＃43;&＃43;) {if (W[i] > j) {dp[i][j] &＃61; dp[i - 1][j];} else {dp[i][j] &＃61; Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] &＃43; V[i]);}}}// 数组最右下角就是最大价值return dp[W.length - 1][C];}public static void main(String[] args) {int[] W &＃61; { 0, 7, 5, 4, 8, 12 };int[] V &＃61; { 0, 13, 8, 20, 11, 6 };System.out.println(knapsack(W, V, 20));}
}


设物品个数 n&＃xff0c;背包最大容量 m&＃xff0c;因双层循环所以上面代码的时间复杂度$O(n\ast m)$&＃xff0c;空间复杂度即二维数组的空间也是$O(n\ast m)$。

优化主要是对二维数组的优化&＃xff0c;从上面的状态转移方程可以看出&＃xff0c;下一行的数据只与上一行的数据有关&＃xff0c;更确切的说&＃xff0c; 任意 F[ i ] [ j ] 的结果只与它上一行左边的 F[ i-1 ] [ 0 ] ~ F[ i-1 ] [ j ] 这一部分区间数据相关。利用这一特点可以将二维数组优化为一维数组。

优化过程网上看了很多都没有讲的太详细&＃xff0c;理解了好久~

如果上面的dp数组是保留2行的话&＃xff0c;相信很多人都知道怎么优化&＃xff0c;可以通过滚动数组来解决。其实2行1行道理都差不多&＃xff0c;上面说了&＃xff0c;对于任意 F[ i ] [ j ] 的结果只与它上一行左边的这一部分区间数据相关&＃xff0c;还是这张图

假设以物品序号和背包容量为坐标描述的话&＃xff0c;(1,20)位置的值13只与(0,0)~(0,20)处的数据有关&＃xff0c;对于第一行的数据填写时&＃xff0c;从右往左填写&＃xff0c;而得到的值并不是直接写在(1,20)的位置上&＃xff0c;而是写在上一行相同的位置(0,20)&＃xff0c;为什么可以这么写&＃xff1f;因为下次确定(1,19)处的值的时候已经用不上这个位置的数据了。

因此&＃xff0c;虽然只有一行数据&＃xff0c;但却包括了逻辑上的两行&＃xff0c;每次所填写的位置左边的数据都属于上一行的数据&＃xff0c;填写位置及右边的数据都属于下一行&＃xff0c;理解了这&＃xff0c;就能明白为什么不能从左往右填写&＃xff1a;因为第二行新的数据会覆盖第一行可能后面还要参与计算的数据。

这样从右往左填写一遍便可以得到第一行的所有数据&＃xff0c;类似的得到第二行&＃xff0c;第3行…&＃xff0c;直到最后一行&＃xff0c;而事实上需要的也仅是最后一行的最后一个位置上的数字。

优化后新的状态转移方程&＃xff1a;F[ j ] &＃61; max( F[ j ] ,F[ j-W[ i ] ] &＃43; V[ i ] )&＃xff0c;
方程中括号外面的 F[ j ] 相当于原方程中的 F[ i ] [ j ]&＃xff0c;
括号里面的 F[ j ] 相当于原方程中的 F[ i-1 ] [ j ]&＃xff0c;
括号里面的 F[ j-W[ i ] ] &＃43; V[ i ] 相当于原方程中的 F[ i-1 ] [ j-W[ i ] ] &＃43; V[ i ]。
对比原新方程可以发现&＃xff0c;区别就是少了表示行数的 i 。

优化后的代码

public class Knapsack_01 {public static int knapsack(int[] W, int[] V, int C) {int[] dp &＃61; new int[C &＃43; 1];for (int i &＃61; 1; i < W.length; i&＃43;&＃43;) {for (int j &＃61; C; j >&＃61; 1; j--) {if (W[i] < j)dp[j] &＃61; Math.max(dp[j], dp[j - W[i]] &＃43; V[i]);}}return dp[C];}public static void main(String[] args) {int[] W &＃61; { 0, 7, 5, 4, 8, 12 };int[] V &＃61; { 0, 13, 8, 20, 11, 6 };System.out.println(knapsack(W, V, 20));}
}


优化后的时间复杂度不变还是$O(n\ast m)$&＃xff0c;而空间复杂度减小到了$O(m)$。

将没有优化过的状态转移方程反向运用

int j &＃61; C;
for (int i &＃61; W.length - 1; i >&＃61; 1; i--) {if (dp[i][j] &＃61;&＃61; dp[i - 1][j - W[i]] &＃43; V[i]) {System.out.print("物品" &＃43; i &＃43; " ");j &＃61; j - W[i];}
}