又例如：
求节点1到节点6的最短路径。用贪心法得19，而实际为17。
显然贪心算法不能对所有问题都能得到最优解,但是对很多问题(包括很多著名的问题）都能产生整体最优解。例如，我们今天要讲的图的单元最短路径问题、最小生成树问题。在有些情况下,算法不能得到整体最优解,但是结果确是最优解的很好近似。
8．1.２贪心选择性质
对于任意一个顶点 ，假如我们使用 表示源顶点到顶点 的最短路径，最后，我们可以证明上述的贪心法结束后有 。
三、算法DIJＫSTRA
输入:含权有向图G＝(V，Ｅ)， V＝{1，２,…ｎ}
输出:Ｇ中顶点1到其他顶点的距离
1. ; ；
２. For y←2 to n
If y相邻于１ tｈen
Eｌsｅ ;
End if
√对于情形(Ａ)，
算法要求
归纳假设
二、算法思想
开始时，我们将所有的顶点划分为两个集合 。所有已经计算好的顶点存放在 中, 中表示还没有计算好的。 中的每个顶点 有一个对应的量 ，该值是从源顶点到 （并且只经由 中的顶点)的最短路径值。
（1）下面就是选择一个 最小顶点 ,并将其ห้องสมุดไป่ตู้动到 中。
（2）一旦 被从 移动到 中， 中每个和 相邻的顶点 的 都要更新：表示经由 到 的一条更短的路径被发现了。
（手工解该题目）
算法的详细实现:
（1）有向图用邻接表来表示 如图
（2）假设每条边是非负的
（3）Ｘ和Y集合用两个向量来表示X［１..n] ,Ｙ［1..n]。初始时X[1]=1,Y［１]＝0.并且对于２<=i<＝ｎ, X[i］=0,Y[i］=1. 因此，执行 的操作,就是X［y]=1, 的操作就是,Y[y］=0。
五、证明
下面来证明，使用该DIＪKＳTRＡ方法得到的是最优解,也就是 。其中， 表示源顶点到顶点 的最短路径； 是从源顶点到 （并且只经由 中的顶点)的最短路径值。
证明: 归纳法
（1）显然
（2）假设,当前将 移动到 中，并且在 之前移动到 中的任何一个顶点 ，都有 。由于 是有限的,也就是说必定存在一条从１到 路径,长度为 (我们需要来证明 ）。
那么这条路径总可以写作：
:1→[ ］→[ ]→。。。→［ ]→[ ]→[ ]→ｙ
在上述序列中，我们总是可以找到一个顶点,不妨称之为 （ ),使得 之后的顶点均属于 ,并且x是在y前最迟离开Ｙ的顶点。所以有以下两种情形:
1→[ ]→［ ]→。。。→［ ]→[x ]→y (A)
或是
1→[ ]→[ ]→。。。→[ｘ ]→[ ]…→y (B)
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到,即贪心选择来达到。这是贪心算法可行的第一个基本要素．也是贪心算法与动态规划算法的主要区别：
动态规划算法：每步所做出的选样往往依赖于相关子问题的解,因而只有在解出相关子问题后．才能做出选择。
贪心算法：仅在当前状态下做出最好选样，即局部最优选则。然后再去解做出这个选择后产生的相应的子问题。贪心算法所做出的贪心选则可以依赖于以往做过的选则，但决不依赖于将来所做的选样,也不依赖于子问题的解。
８.3单源最短路径问题(狄斯奎诺Ｄijkstrａ’ｓ算法)
一、问题描述
是一个有向图，每条边上有一个非负整数表示长度值，其中有一个顶点 称为源节点。所谓的单源最短路径问题就是:求解该源节点到所有其它节点的最短路径值。不失去一般性，我们假设 并且 ＝1。那么该问题可以使用Dｉjｋｓｔrａ’s算法来求解，该算法是一种贪心算法，并且能求得最优解。
6. ｅｎd for
7. for ｊ←1 tｏ n-1
8. 令 ，找到最小
9. Ｘ←Ｘ∪{y} ／*将 从 移动到 中
10 Y←Ｙ-{y}
For 每条边{y，ｗ}
If w∈Ｙ and +lengｔh[y，w]＜ then
/＊更新 中和 相邻顶点的 值
14.enｄfor
15.end ｆor
四、举例说明:
通常是：先拿两个2角5分的＋1个一角+3个一分
这种找法所拿出的硬币个数最少。这种算法其实就是贪心算法。顾名思义:该算法总是作出在当前看来最好的选择,并且不从整体上考虑最优问题,所作出的选择只是在某种意义上的局部最优解。
上面的解法得到的恰好也是最优解。因此，贪心方法的效率往往是很高的。
假如，面值有一角一分、五分和一分，要找给顾客一角五分。如果还是使用上述贪心算法,得到的解是：一个一角一分+4个一分。而最优解是3个５分。
动态规划：是自底向上的方法解各子问题；
贪心算法:是自顶向下的方法。每做出一次贪心选择就将所求问题简化为规模更小的子问题.
使用贪心法的难点在于:证明所设计的算法确实能够正确解决所求解的问题。即对于一个具体的问题，必须证明每一步所做出的贪心选择最终导致问题的整体最优解。
首先,考察问题的一个整体最优解，并证明可修改这个最优解,使其以贪心选择开始。做出贪心选择后.原问题简化为规模更小的类似子问题。然后，用数学归纳法证明、通过每一步做贪心选择.最终可得到问题的整体最优解。
第八章－贪心算法
———————————————————————————————— 作者：
———————————————————————————————— 日期:
ﻩ
第8章 贪心算法
８.1简介
８．1.1例子
例子: 有4种硬币，面值分别为2角5分、一角、五分和一分。现在要求以最少的硬币个数找给顾客６角三分。
背包问题：
给定ｎ种物品 和一个背包,物品i的体积为 ，价值为 。已经知道背包的承重量为C。
假设 是物体i被装入背包的部分， ；要求装满背包且背包内物体价值最大。
mａx
选择方法：目标函数的值增加最快，而包载容量的消耗较慢的物体装入包中。故优先选择价值体积比最大的物体装入背包。
背包与０-1背包的区别：
结论0-1背包问题能用动态规划法解,但不能用贪心法解。
其中，证明贪心选择后的问题简化为规模最小的类似子问题的关键在于利用该问题的最优子结构性质。
最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。
贪心算法和动态规划算法都要求问题具有最优子结构性质,这是两类算法的一个共同点。但是都具有最优子结构的问题该选则贪心法还是动态规划算法求解?是否能用动态规划法的也能用贪心算法解？