由浅入深了解贪心算法
-
贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。 贪心算法一般按如下步骤进行:①建立数学模型来描述问题。②把求解的问题分成若干个子问题。③对每个子问题求解,得到子问题的局部最优解。④把子问题的解局部最优解合成原来解问题的一个解。 贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,省去了为找最优解要穷尽所有可能而必须耗费的大量时间。 贪心算法采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪心算法不要回溯。 但并不是所有问题都可以用贪心算法来求解的,因为它每次拿到的只是局部最优解,局部最优解组合起来并不一定是全局最优解。 算法里有一个经典例题:有一个小偷,他进到了一个店里要偷东西,店里有很多东西,每个东西的价值是v,每个东西的重量是w。但是小偷只有一个背包,他背包总共能承受的重量是W。请问怎么拿东西能让他拿到的价值最大? 这个问题用我们平时的思维也很好想,要拿到总价值最大,那我们就贪呗,就拿最贵的,即价值除以重量的数最大的。但是每次都拿最贵的,是不是最后总价值最大呢?我们先假设上面的例子是0-1背包,最贵的是v1,然后是v2,v3。我们先拿v1, 背包还剩40,拿到总价值是60,然后拿v2,背包还剩20,拿到总价值是160。然后就拿不下了,因为v3的重量是30,我们背包只剩20了,装不下了。但是这个显然不是全局最优解,因为我们明显可以看出,如果我们拿v2,v3,背包刚好装满,总价值是220,这才是最优解。所以0-1背包问题不能用贪心算法。 但是分数背包可以用贪心算法,因为我们总是可以拿最贵的。我们先拿了v1, v2,发现v3装不下了,那就不装完了嘛,装三分之二就行了。 贪心算法的重点就在一个贪字,要找到贪的对象,然后不断的贪,最后把目标贪完,输出最优解。要注意的是,每次贪的时候其实拿到的都只是局部最优解,局部最优解不一定组成全局最优解。
西南地区IT社群(QQ)
- 云南
- 【昆明网页设计交流吧】243627302
- 【昆明nodejs交流吧】 243626749
- 【VUE】838405306
- 【云南程序员总群】343606807
- 【昆明UI设计】104031254
- 【云南软件外包】15547313
- 贵州
- 【PHP/java源码/站长交流群】55692114
- 四川
- 【成都Java/JavaWeb交流】86669225
- 【vaScript+PHP+MySql】116270060
- 【UI设计/设计交流学习群】135794928
- 重庆
- 【诺基亚 JAVA游戏博物馆】 559479780
- 【PHP,Java,Python,C++接单】 442103442
- 西藏