【算法设计】背包有关问题2

2012-11-26

【算法设计】背包问题2之前整理了屈奶奶讲的背包问题，感谢cyh24童鞋留言，传我一份武林秘籍《背包问题九讲》，实

【算法设计】背包问题2

之前整理了屈奶奶讲的背包问题，感谢cyh24童鞋留言，传我一份武林秘籍《背包问题九讲》，实践了一下文档里对空间复杂度的改进。

0-1背包问题通过之前的分析，Fk(y) 表示只允许装前k 种物品,背包总重不超过y 时背包的最大价值。得到0-1背包的递推公式和边界条件：【算法设计】背包有关问题2

对空间的优化主要在Fk(y)，原本我们用两个循环实现：



递归公式最主要的区别是Fk(y-wk)+vk，而非原来的Fk-1(y-wk)+vk，即物品可以在前k件中继续挑选。用一维数组时希望此时F[y]的数值即为F[k-1][y]的数值，而F[y-w]的数值为改变之后的F[k-1][y-w]的数值。因此我们可以用顺序0...B（而非逆序B...0）实现：


代码及文档下载：http://download.csdn.net/detail/xiaowei_cqu/4787977参考资料：dd_engi等 《背包问题九讲》
（转载请注明作者和出处：http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途）

热点排行

编程

【算法设计】背包有关问题2

（转载请注明作者和出处：http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途） a("article_content_down");

（转载请注明作者和出处：http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途）