说明
这段时间每天加班, 确实没有整块的时间来写博客了, 一不小心就到周末了, 要是不写篇博客, 那就又要鸽了. 为了不打脸, 还是加班加点的把这篇博客给写了出来.
再说个题外话, 最近一直在看一本关于 MySQL 的掘金小册, 感觉很棒, 作者用通俗易懂的语言将 MySQL 的底层原理进行了介绍, 图文并茂, 讲解的很深入, 可以看出作者应该是花了不少心思, 借阅了不少书籍的. 据说作者是个 95 后, 为了写这本小册子还特意辞了职, 简直优秀!
一篇文章大概需要花费 40~60 分钟, 建议花整块的时间进行阅读.
从作者的身上, 也看到了一种匠心精神, 反观自己, 写这么水的文章, 实在是惭愧. 所以决定对文章质量把把关, 本着宁缺毋滥的原则来写作, 尽量不浪费大家的时间.
好了, 闲话就说到这了, 言归正传.
上一篇中, 我们了解了 01 背包问题, 并用三种方法进行了求解, 但其实在最后一种解法上, 我们还能再对它的空间复杂度进行优化.
优化过程
已经过去一个星期了, 可能一部分人已经忘记了之前的解题思路, 所以在这里把之前填表法使用到的图贴了过来:
这是我们上一篇填表法的最终结果, 在这里, 聪明的你应该能发现, 其实这里大部分的内容都没有用上, 那么让我们来想想, 如何优化一下空间复杂度呢?
再回头看下之前的递推关系式:
可以发现, 每次求解 KS(i,j)只与 KS(i-1,m) {m:1...j} 有关. 也就是说, 如果我们知道了 K(i-1,1...j)就肯定能求出 KS(i,j), 为了更直观的理解, 再画一张图:
下一层只需要根据上一层的结果即可推出答案, 举个栗子, 看 i=3,j=5 时, 在求这个子问题的最优解时, 根据上述推导公式, KS(3,5) = max{KS(2,5),KS(2,0) + 3} = max{6,3} = 6; 如果我们得到了 i=2 时所有子问题的解, 那么就很容易求出 i=3 时所有子问题的解.
因此, 我们可以将求解空间进行优化, 将二维数组压缩成一维数组, 此时, 装填转移方程变为:
KS(j) = max{KS(j),KS(j - wi) + vi}
这里 KS(j - wi)就相当于原来的 KS(i-1, j - wi). 需要注意的是, 由于 KS(j)是由它前面的 KS(m){m:1..j}推导出来的, 所以在第二轮循环扫描的时候应该由后往前进行计算, 因为如果由前往后推导的话, 前一次循环保存下来的值可能会被修改, 从而造成错误.
这么说也许还是不太清楚, 回头看上面的图, 我们从 i=2 推算 i=3 的子问题的解时, 此时一维数组中存放的是 {0,0,2,4,4,6,6,6,6,6,6}, 这是 i=2 时所有子问题的解, 如果我们从前往后推算 i=3 时的解, 比如, 我们计算 KS(0) = 0,KS(1) = KS(1) = 0 (因为 j=1 时, 装不下第三个珠宝, 第三个珠宝的重量为 5),KS(2) = 2,KS(3) = 4,KS(4) = 4, KS(5) = max{KS(5), KS(5-5) + 3} = 6,....,KS(8) = max{KS(8),KS(8 - 5) + 3} = 7. 在这里计算 KS(8) 的时候, 我们就把原来 KS(8)的内容修改掉了, 这样, 我们后续计算就无法找到这个位置的原值(这个栗子没举好.. 因为后面的计算没有用到 KS(8)= =), 也就是上一轮循环中计算出来的值了, 所以在遍历的时候, 需要从后往前进行倒序遍历.
- public class Solution{
- int[] vs = {0,2,4,3,7};
- int[] ws = {0,2,3,5,5};
- int[] newResults = new int[11];
- @Test
- public void test() {
- int result = ksp(4,10);
- System.out.println(result);
- }
- private int ksp(int i, int c){
- // 开始填表
- for (int m = 0; m <vs.length; m++){
- int w = ws[m];
- int v = vs[m];
- for (int n = c; n>= w; n--){
- newResults[n] = Math.max(newResults[n] , newResults[n - w] + v);
- }
- // 可以在这里输出中间结果
- System.out.println(JSON.toJSONString(newResults));
- }
- return newResults[newResults.length - 1];
- }
- }
输出如下:
- [0,0,0,0,0,0,0,0,0,0,0]
- [0,0,2,2,2,2,2,2,2,2,2]
- [0,0,2,4,4,6,6,6,6,6,6]
- [0,0,2,4,4,6,6,6,7,7,9]
- [0,0,2,4,4,7,7,9,11,11,13]
- 13
这样, 我们就顺利将空间复杂度从 O(n*c)优化到了 O(c). 当然, 空间优化的代价是, 我们只能知道最终的结果, 但无法再回溯中间的选择, 也就是无法根据最终结果来找到我们要选的物品组合.
关于初始值
01 背包问题一般有两种不同的问法, 一种是 "恰好装满背包" 的最优解, 要求背包必须装满, 那么在初始化的时候, 除了 KS(0)为 0, 其他的 KS(j)都应该设置为负无穷大, 这样就可以保证最终得到的 KS(c)是恰好装满背包的最优解. 另一种问法不要求装满, 而是只希望最终得到的价值尽可能大, 那么初始化的时候, 应该将 KS(0...c)全部设置为 0.
为什么呢? 因为初始化的数组, 实际上是在没有任何物品可以放入背包的情况下的合法状态. 如果要求背包恰好装满, 那么此时只有容量为 0 的背包可以在什么都不装且价值为 0 的情况下被 "恰好装满", 其他容量的背包均没有合法的解, 因此属于未定义的状态, 应该设置为负无穷大. 如果背包不需要被装满, 那么任何容量的背包都有合法解, 那就是 "什么都不装". 这个解的价值为 0, 所以初始状态的值都是 0.
总结
01 背包问题可以用自上而下的递归记忆法求解, 也可以用自下而上的填表法求解, 而后者可以将二维数组的解空间优化成一维数组的解空间, 从而实现空间复杂度的优化.
对于 01 背包问题的两种不同问法, 实际上的区别便是初始值设置不一样, 解题思路是一样的.
关于 01 背包问题, 介绍到这里就已经全部结束了, 希望能对大家有所帮助. 如果觉得有收获, 不要吝啬你的赞哦, 也欢迎关注我的公众号留言交流.
来源: https://www.cnblogs.com/mfrank/p/10587463.html