算法之贪心算法
浏览数：18 /
时间：2015年06月08日
所谓贪心就是指永远找最大的，在求解问题时，总是做出最好的选择，它得到的是局部的最优解，并不是对所有问题都能得到整体最优解。
其有两个重要的子特性：
1、最优子结构：假如将子结构的一部分去掉，剩下的子结构还是最优子结构。
2、贪心选择性：找单位价值最大的那个。
重点：将给出的一系列问题求解其单位价值（单位路程等），按照其单位价值从大到小（路程从小到大）依次排序。在用贪心算法只需要依次取即可。对于不足的部分可以将其分割，求部分价值。
举例：就像是背包问题，求重量不超过背包重量100时的最大价值。（w表示物品重量，v表示价值，v/w表示单位重量价值，顺序已经排好，如下表）
根据上面的步骤，只需要按照排好序的依次取出放到包中，如1,2,3物品总重量为90，其价值和为115.还剩下重量为10的没有装，这时就只需要将物品4分割出重量10放到保重就可以得到最大价值：v=65+20+30+（40/50）*60=163。
总结：做贪心算法，重要的是注意如下两点：
1、将各个物品的单位价值进行从大到小排序
2、单个物品可以分割计算价值
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
