一道贪心法的题目，仅供参考

lllaaa

<>请各位看看做的有没有问题。</P><BR>

erupt

我想看看

erupt

我想看看

lshysky

<p>去看看</p><p>正在学习中</p>

okhaoba

<p>请问，什么是贪心算法？</p>

madio

<div class="box2"><span class="Tit">贪心算法</span></div><table class="htb wr" cellspacing="0" cellpadding="0" width="100%" border="0"><tbody><tr><td><div class="box2 p14">贪心算法<br/><br/>一、算法思想<br/><br/>贪心法的基本思路：<br/>——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。<br/>该算法存在问题：<br/>1. 不能保证求得的最后解是最佳的；<br/>2. 不能用来求最大或最小解问题；<br/>3. 只能求满足某些约束条件的可行解的范围。<br/><br/><br/>实现该算法的过程：<br/>从问题的某一初始解出发；<br/>while 能朝给定总目标前进一步 do<br/>　　 求出可行解的一个解元素；<br/>由所有解元素组合成问题的一个可行解；<br/><br/>二、例题分析<br/><br/>1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。<br/>要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。<br/><br/>物品 A  B  C D E F G <br/>重量 35  30  60  50  40  10  25  <br/>价值  10  40  30 50  35  40  30 <br/><br/><br/>分析：<br/><br/>目标函数： ∑pi最大<br/>约束条件是装入的物品总重量不超过背包容量：∑wi&lt;=M( M=150)<br/><br/><br/>（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？<br/>（2）每次挑选所占重量最小的物品装入是否能得到最优解？<br/>（3）每次选取单位重量价值最大的物品，成为解本题的策略。 ?<br/><br/><br/>值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。<br/>贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。<br/>可惜的是，它需要证明后才能真正运用到题目的算法中。<br/>一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。<br/>对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：<br/><b>（1）贪心策略：选取价值最大者。</b>反例：<br/>W=30<br/>物品：A  B  C<br/>重量：28 12 12<br/>价值：30 20 20<br/>根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。<br/><b>（2）贪心策略：选取重量最小。</b>它的反例与第一种策略的反例差不多。<br/>（3）贪心策略：选取单位重量价值最大的物品。反例：<br/>W=30<br/>物品：A  B  C<br/>重量：28 20 10<br/>价值：28 20 10<br/>根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。<br/><br/>所以需要说明的是，贪心算法可以与<b>随机化算法</b>一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）<br/><br/>三种常见贪心算法总结：<a href="http://hi.baidu.com/anonympine/blog/item/90cd0cd7517828dfa044df30.html" target="_blank">http://hi.baidu.com/anonympine/blog/item/90cd0cd7517828dfa044df30.html</a>
                                                <br/></div></td></tr></tbody></table>

wsg0124

参考一下！

sydjun

好好学习。。。。。。。。。。。。

jingxingde

好好学习。。。
* b0 R, Z# D- n9 K$ N! `! U" o

superDi

刚好~~在看这类算法~~收下~~