0-1背包问题

作者：sunpy 来源：不详发布时间：2008/07/31 发布人：admin

sunpy 发布留言 2008-7-30 08:51

0-1背包问题

在网上找到了这句话：
如果我们采用回溯法解决这个问题，我们采用如下的搜索策略：只要一个结点的左儿子结点是一个可行结点就搜索其左子树；而对于右子树，我们需要用贪心算法构造一个上界函数[[这个函数表明这个结点的子树所能达到的可能的最大容量（因为只有将0-1背包问题改变为背包问题才可能利用贪心算法，因此这个上界函数在绝大多数情况下不会是上确界函数）]，只在这个上界函数的值超过当前最优解时才进入搜索。随着搜索进程的推进，最优解不断得到加强，对搜索的限制就越来越严格。

我的问题是为什么要在其右子树上使用贪心算法？
左子树和右子树有什么区别？

leeco 发布留言 2008-7-30 10:53

我想他的意思是只有在“当前背包总值+剩余物品总值在可以分割的情况下可以取到的最大价值>当前最优值”成立时才可能得到更优解

事实上，当前背包总值+剩余物品总值在不可以分割的情况下可以取到的最大价值>当前最优值，成立时，一定可以得到更优解，但是“剩余物品总值在不可以分割的情况下可以取到的最大价值”是和原问题同类型的问题，不可能为了剪支再去搜索求解这个值。
所以就把这个得到更优解的充要条件调整为一个必要条件。

sunpy 发布留言 2008-7-30 16:18

好像懂了一点点，谢谢！

页: [1]

特别说明：如网页特效代码中有引用图片文件等，请自己下载到本地调试！

[] [返回] [打印] [收藏] [评论]

上一篇代码：Exp 函数可e（自然对数的底）的幂次方？

下一篇代码：安装VC++6.0要不要注册环境变量？

0-1背包问题

0-1背包问题

精品推荐

代码分类

阅读排行

相关代码