大家好，今天小编来为大家解答动态规划01背包问题优化这个问题，很多人还不知道，现在让我们一起来看看吧！
在上一篇文章中，用于记忆搜索的数组定义为：
memo[i,j]表示选择前i个物品（包括i个物品）放入负载为j的背包中可以获得的最大值。
一、只用二行的空间
根据其状态转移方程：
此时要解决的问题可以分解为求下面两个问题的最大值
(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(‘无效的w 或v’); if(C 0) throw new IllegalArgumentException(‘C 必须大于或等于零。’); int n=w.长度； if(n==0 || C==0) 返回0; int[][] 备忘录=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]]); } 返回备忘录[(n-1) % 2][C]; } public static void main(String[] args) { }} 需要的存储长度仅为2(C+1)，此时空间复杂度为O(C)
2.仅使用一行空间
因为当前行是根据上一行的比较来计算的，所以每个计算结果都可以直接放入上一层的方格中。
1.刚开始，除了第一个，其他都是6个
2、当放入ID为1的物品进行计算时，容量从最后一位开始计算到5，原来的6与10+6=16进行比较，所以容量为5的位置改为16。
3、当ID为1的item被移动到容量为4的元素时，容量为2的item将会与容量为4的item进行比较。
4.此时也替换为16
5. 返回并比较1 和3，并将其替换为16。
6、继续前进，比较元素0和2，就会有差异。
7、因为容量只有2，所以只能放下10这个值，比6大，所以替换成10。
8、具体代码实现如下
原创文章，作者：小su，如若转载，请注明出处：https://www.sudun.com/ask/98420.html
用户评论
稳妥
看了你的文章之后感觉对01背包问题的思路有了新的认识，动态规划确实是个好用的工具！之前一直用蛮力法解决这个问题，效率 really 太低了。这篇文章把核心思想解释得很通俗易懂，而且代码实现也很清晰简洁！感谢分享
有6位网友表示赞同！
不离我
01背包问题真是个经典的算法题，这篇文章分析得很透彻，把动态规划的空间状态和时间复杂度都解释清楚了。我之前也尝试过解决它，但总觉得思路很混乱，现在看来你的方法简直就是最佳方案！
有13位网友表示赞同！
軨倾词
标题说的没错，优化真的有很大的意义！我曾经用暴力法刷题的时候感觉效率太低，后来发现了动态规划这种技术，时间复杂度降低了许多。这篇博客的代码实现也很好参考，我现在会去尝试一下。
有19位网友表示赞同！
巷口酒肆
这篇文章虽然讲解清楚了01背包问题的解决思路，但对于初学者来说可能还是有点难度，毕竟需要对动态规划的基础有了一定的了解才能真正理解其中的原理。也许可以增加一些更加基础的例子帮助读者更快上手
有11位网友表示赞同！
歆久
我对动态规划不太熟悉，来这里学习一下，你的文笔比较清晰流畅，把01背包问题解题思路总结得很好！特别是空间状态的设计和表格的构建方法，我感觉很有启发性，我会尝试用这个方法来解决其他算法问题。
有10位网友表示赞同！
浮光浅夏ζ
虽然标题说的对“优化” ，但我还是觉得这篇文章写的有点过于复杂了，对于一些入门级的读者来说可能有点看不懂，建议多用通俗易懂的语言来描述问题和解决方法。
有20位网友表示赞同！
?亡梦爱人
感觉动态规划真的能把问题的复杂度降到最低。这篇博文解释的很仔细，从状态转移方程到递推公式都说得清清楚楚！我现在对01背包问题的优化思路有了更深的理解。
有13位网友表示赞同！
颓废i
这篇文章的解题方法很简洁高效，我对动态规划的应用有了新的启发，以后遇到类似的问题可以直接参考这段代码来解决。感谢作者分享这种实用的解题技巧！
有11位网友表示赞同！
暖瞳
文章写的不错，把01背包问题的关键点提得很清楚，但我还是有些不太理解空间状态的设计思路，希望能提供更多例子帮助我理解。
有16位网友表示赞同！
留我一人
我觉得动态规划的本质是将复杂问题分解为一系列小的子问题，然后通过重复计算和存储中间结果来实现高效的求解。这篇文章的分析方法非常到位，有助于我对动态规划有了更深入的认识！
有10位网友表示赞同！
心亡则人忘
很感谢作者分享这篇关于01背包问题的优化文章，让我了解了动态规划这个强大的算法工具。我已经开始尝试将它应用到其他算法问题中，相信会有不错的效果!
有13位网友表示赞同！
青楼买醉
我曾经也研究过01背包问题，用了暴力法实现，效率是真的太低了！看了这篇文章才恍然大悟，原来可以用动态规划来优化，感谢作者让我看到了更好的解决思路。
有14位网友表示赞同！
何年何念
我觉得本文还是缺少一些实例代码的帮助，比如可以提供几种不同的输入数据和对应的输出结果，这样更容易理解文章里的概念！
有16位网友表示赞同！
闲肆
对于初学者来说，文章可能稍微有点难懂，建议加入更详细的讲解和例子，帮助他们更好地理解动态规划的概念。
有17位网友表示赞同！