动态规划解决背包问题的方法（动态规划之0-1背包问题优化）

上篇文章中，讲述了动态规划之0-1背包问题及其解决方法。它的时间复杂度和空间复杂度都为：O(n * C)， 其中n为物品个数; C为背包容积。

在时间复杂度方面已经达到了最优，但是空间复杂度方面还是可以进行优化的。下面将说明如何优化。

在上篇文章，其记忆化搜索的数组定义为：

memo[i,j] 表示在前i件（包括i件）物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。

根据它的状态转移方程：

这时要求解的问题可以化解为求下面2个问题的最大值

（1）第i个物品不放进背包里，这时的价值就是i-1时的价值：F(i-1,c)

（2）如果第i个可以放入来，且不超过容量C，这是的价值为第i个物品的价值加上前面i-1的价值，注意这时i-1的重量为c-w(i)：v(i) F(i-1, c-w(i) )

真正影响结果的只是当前行与前一行的数据，因此可以用行数 i%2 的值来作为保存的行，奇数行或者偶数行。

行数的变化为：

千言万语还不如直接看代码来得实际。

看其实现：

/// 背包问题 /// 动态规划改进: 滚动数组 /// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积 /// 空间复杂度: O(C), 实际使用了2*C的额外空间 public class Solution1 { public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C < 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; int[][] memo = new int[2][C 1]; for(int j = 0 ; j <= C ; j ) memo[0][j] = (j >= w[0] ? v[0] : 0); // 变化的地方加入% for(int i = 1 ; i < n ; i ) for(int j = 0 ; j <= C ; j ){ memo[i % 2][j] = memo[(i-1) % 2][j]; if(j >= w[i]) memo[i % 2][j] = Math.max(memo[i % 2][j], v[i] memo[(i-1) % 2][j - w[i]]); } return memo[(n-1) % 2][C]; } public static void main(String[] args) { } }

需要的存储长度只为2(C 1)，此时空间复杂为O(C)

二、只用一行的空间

因为当前行都是在上一行的基础上比较计算得到的，因此可以将每次的计算结果直接放到上一层的方格里。

1、刚刚开始，除了第一个外，其它的都是6

2、当把id为1的物品放入进行计算时，从最后一个往回计算容量为5为，原来的6与10 6=16作比较，所以容量为5的位置修改为16

3、id为1的物品，移动为容量为4的元素时，是容量为2与容量为4的作比较

4、这时也是用16替换

5、再往回移动比较1和3，一样的用16替换

6、一样再往移动比较0和2的元素，这时会有不同

7、因为容量只有2，所以只能放下10的价值，比6大，替换为10

8、具体的代码实现如下

因为长度只为C 1，所以不再需要二维数，只用一维数据存储结果的缓存就可以。

/// 背包问题 /// 动态规划改进 /// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积 /// 空间复杂度: O(C), 只使用了C的额外空间 public class Solution2 { public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C < 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; int[] memo = new int[C 1]; for(int j = 0 ; j <= C ; j ) memo[j] = (j >= w[0] ? v[0] : 0); for(int i = 1 ; i < n ; i ) for(int j = C ; j >= w[i] ; j --) memo[j] = Math.max(memo[j], v[i] memo[j - w[i]]); return memo[C]; } public static void main(String[] args) { } }

需要的存储长度只为C 1，此时空间复杂为O(C)