Question

用贪心算法能求解背包问题吗?为什么,理由是什么?

Answer 1

贪心算法是种策略，思想。。。
它并没有固定的模式
比如最简单的背包问题
用贪心的思想去做，就可能有很多种方法
性价比最高的、价值最高的、重量最轻的
而你没办法确保你所选择的贪心策略对所有的情况都是绝对最优的

动态规划的思想是分治+解决沉余
把一个复杂的问题分解成一块一块的小问题
每一个小问题中得到最优解
再从这些最优解中获取更优的答案
典型的例子数塔问题
画个图就能看出来

Answer 2

不可以。
贪心法在求背包问题时误解太多，不易得分，实在做不明白才可以勉强一试……好坏能骗上至少20分。

Answer 3

我也是在网上找背包问题的贪心算法和动态规划，不过贪心法肯定能求解背包问题了，虽然它要求每步都得最大解，但如果一个方案不能满足题目大的要求，就会否定此方案，继续枚举其他的方案，直到遇到第一个满足题目要求的就为贪心法结果，是可行解但不一定是最优解。关键是自己设定评判要求。我在搜索中。。。。

Answer 4

这个你可以参考贪心算法性质的证明，背包问题是按照单位质量价值大的先加入
这就符合贪心算法先取最接近背包容量的C的方法。

Answer 5

一般的贪心策略都会造成解的丢失,动态规划则是相当于枚举了所有的解.

如果你有一个很好的贪心策略,背包问题也能用贪心策略来解决.但是,你是很难找到一个很好的贪心策略的.