贪心算法--概论

贪心（贪婪）算法

算法思想：算法的每一步都可以实现当前的最优状态，但整体上不一定可以获得最优解。
1）贪心算法不追求最终的最优解；
2）贪心算法每一步都是最优解。

关于贪心准则：
1）一个经过N步解决的问题，其每一步都必须应用贪心准则。
2）准则一旦确定，不再更改。

优点：算法简单、快。
缺点：着眼于局部；整体上，可以得到最优解的近似解。

贪心算法应用

1）找零问题

要求找出的硬币个数尽量少

• 存在面额为：25美分、10美分、5美分、1美分的硬币
  找零67美分：25*2+10*1+5*1+1*2（得到最优解）
• 存在面额为：8美分、5美分、1美分的硬币
  找零20美分：8*2+1*4（不是最优解，最优解为5*4）

2）装箱问题

问题描述：
n个物品体积分别为：V1、V2、…、Vn。将这n个物品装入若干个体积为V的箱子（约定每个物品的体积Vi都不超过V）。要求：使用的箱子尽可能少。
贪心准则：
1）将所有物品按体积大小降序排列；
2）每次都保证将未放入箱子中体积最大的物品优先放入已打开的箱子中。

3）迷宫

问题描述：
在一个含有m*n的迷宫中，用0表示路径，用1表示墙壁，设置入口坐标及出口坐标，查找从入口坐标到出口坐标的一条全0的路。
贪心准则：
从当前位置到下一位置优先出口方向探测。

4）勇士斗恶龙

问题描述：
n个头的恶龙，m个骑士。一个能力为x的骑士可以砍掉恶龙一条直径不超过x的头，且需要支付给骑士x个金币。如何雇用骑士才能砍掉恶龙所有的头且使用金币最少？注：一个骑士只能砍一个头且不可雇用两次。
贪心准则：
1）将骑士的能力按照升序排列；
2）将恶龙的头直径按照升序排列；
3）如果骑士的能力超过恶龙头直径，则可以雇佣。

5）哈夫曼树