贪心法背包问题证明方法

时间：2013-05-15 05:08:31
【文件属性】：

文件名称：贪心法背包问题证明方法

文件大小：15KB

文件格式：RAR

更新时间：2013-05-15 05:08:31

背包问题

贪心法证明背包问题： 个最优解。 证明基本思想：通过将贪心法的解与任何最优解进行比较来证明。如果这两个解不同，就找出不相等的且下标最小的第一个，从中可推出与假设矛盾的结论。 证明：设X＝(x1,…xn)是KNAPSACK所生成的解，如果所有xi等于1，显然这个解就是最优解，于是设j是使xi≠1的最小下标,由算法可知,对于1≤i ∑vixi. 不失一般性，可假定,∑wiyi=c ，设k是使得yk ≠ xk的最小下标，显然，这样的k必定存在，由上面的假设，可以推得yk j。

立即下载

【文件预览】：
贪心法背包问题.doc

网友评论

  • 感谢！这个作为价值密度优先贪心策略对于分数背包问题的正确性证明的参考了
  • 看起来还可以的样子，学习了
  • 很详细，特别是其中的介绍思路的部分，让我豁然开朗。其实我是在看别的证明，但是看不明白，才上网来找。这个把思路点明了。
  • 内容不怎么详细，不太容易理解
  • 挺好的。。再详细点就看不懂了= =
  • 还行,可以借鉴
  • 谢谢,证明很详细
  • 谢谢,证明很详细
  • 这个资源我用word2010打开，只有几行字，是证明过程，没有代码。

相关文章