贪婪算法的解题思路
[toc]
本来想叫《贪婪算法的设计思想》的，但是觉得写的不够深，纯粹以解题为目的的复习还是不要这么写好。
贪婪法，又称贪心算法，是寻找最优解问题的常用方法，方法模式是在求解过程的每个步骤应用贪心原则：
每个步骤选取当前状态下最好的或最优的选择（局部最有利选择）
问题：最后堆叠的结果不一定是最优解
以题为例：
1.找零钱
有25分、10分、5分、1分四种硬币，对于输入 x ，输出最少找钱数的找钱方案。例如：
输入：41
输出：25 10 5 1
这个问题使用贪婪法可以得到最优解，即每一步选择小于剩余应找钱数的最大硬币。（剩余应找钱数 = x - 已找钱数）
但是如果将硬币设置为 25分、20分、5分、1分 四种硬币，
这个时候最优解是：20 20 1，
但是贪婪法结果是：25 5 5 5 1.
2.背包问题
有 N 件物品和一个承重为 C 的背包，每件物品的重量是 wi，价值是 pi，求将哪几件物品放入背包可以使重量不超过 C 的情况下总价值最大。
设置一个价值系数，Vi = pi / wi，那么就又变成一个找零钱问题，在价值系数中挑选最大项并计算剩余的可承重量。
总结
大多数情况下，贪婪法只能得到比较接近最优解的近似的最优解。可作为一种辅助思想，但在一般解题的过程中需要慎重一点。
贪婪法思想的典型应用：最小生成树的 Prim 算法和 Kruskal 算法，Dijkstra 的单源最短路径算法
Dijkstra 为例：
1.获取所有源点可达的直接路径长度（不能直接到达的设为∞）设为 dis[];
2.找到离源点最近的一个顶点，以其为拓展，得到以其为中间点的可达最短路径，并更新 dis[];
3.在未拓展过的顶点中重复步骤2，最后得到源点到其他点的所有最短路径。
关于怎么正确的解决0-1背包问题，请看：动态规划-0-1背包问题
