文档介绍：该【贪心算法贪婪算法 】是由【hezhihe】上传分享，文档一共【18】页，该文档可以免费在线阅读，需要了解更多关于【贪心算法贪婪算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1
基本思想
通过作出在当前看来最优的选择（贪心选择），将原问题规模缩小，如此反复，直至得到最终解。
贪心算法并非对所有问题都能得到整体最优解。
2
贪婪算法每一步所选的结果都是局部的最优解
这么做的目的就是希望经过所有的步骤所得到的解答会是全局最优解
不过事实上的结果并不一定能达到全局最优解.
贪婪算法所花的时间通常较少,且就算不是全局最优解,但最后所得结果也不会太差
3
贪心算法的基本要素
动态规划法，第K步所作出的选择依赖于第K-1步内若干个子问题解，只有在解出K-1步所有子问题后，才能做出选择，贪婪法仅在当前状态下作局部最优选择。
贪心算法与动态规划算法的差异
4
0-1背包问题：
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
5
背包问题：
与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
这2类问题极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
6
用贪心算法解背包问题的基本步骤：
首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
7
2
3
1
6
7
1
2
4
2
3
A
B
1
3
从A点出发到B点,如何找出最短的路程?
8
单源最短路径
给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
9
例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。
10
迭代
S
u
dist[2]
dist[3]
dist[4]
dist[5]
初始
{1}
-
10
maxint
30
100
1
{1,2}
2
10
60
30
100
2
{1,2,4}
4
10
50
30
90
3
{1,2,4,3}
3
10
50
30
60
4
{1,2,4,3,5}
5
10
50
30
60
Dijkstra算法的迭代过程：