PIGWORLD

学无止境

背包问题 -- 2) 改进,自顶向下的动态编程

        在上一篇《背包问题 -- 1) 思路,递归求解》中,我们讨论了用递归的方式来解决背包问题。但是,直接使用递归会造成大量的重复运算,就上一篇中的例子来说,对于容积为17的背包来说,其中两种组合方案为:

        方案一: 4(A) + 5(B) = 9 ,即背包中装一个A物品和一个B物品;

        方案二: 5(B) + 10(C) = 15 ,即背包中装一个B物品和一个C物品;

注意,上面两种方案都需要计算knap(space = cap - item[1].size)(注:1对应B物品)的情况,这就造成了重复计算,而且计算量是成指数增长的。如果我们在第一次计算knap(space = cap - item[1].size)时就保存其返回值,那么在下一次需要用到的时候只需要直接使用这个返回值就行了,而不必再去计算。

        这里我们给出动态编程的定义,即递归程序中,在每一步递归调用前使用已计算的值来完成当前的递归调用

        对于背包问题,我们用一个数组knowKnap[M]来保存每一个可能的space值。按动态编程改进后的程序源代码如下:

http://pigworld.blogbus.com/files/1135354918.jpg

posted on 2006-01-03 23:16 PIGWORLD 阅读(4032) 评论(3)  编辑 收藏 引用

Feedback

# re: 背包问题 -- 2) 改进,自顶向下的动态编程 2006-03-26 15:24 william lee

这个方法可以找到最优解,不过当变量数和容积达到一定程度的时候,计算量将变得非常的大,所以对于大型求解不是很方便。  回复  更多评论   

# re: 背包问题 -- 2) 改进,自顶向下的动态编程 2006-04-16 19:55 willline

能不能把源代码 发给我看看 谢谢!
  回复  更多评论   

# re: 背包问题 -- 2) 改进,自顶向下的动态编程 2006-04-17 21:42 Pigwen

上面写的就是源代码了啊,但是就和william lee说得一样,这个算法不是很实用,计算量太大了~~  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理