贪心算法.ppt

算法设计与分析
北京交通大学计算机学院
李清勇
E-mail: ******@
Tel: 51688603
主校区: 9号楼 北312
回顾-动态规划基本步骤
1）分析最优解的性质，并刻划其而空白长条表示的活动是当前正在检查相容性的活动。
活动安排问题
贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。
解法证明：
若E={e1,e2…en}是按结束时间排序的活动集合，则e1具有最早的结束时间，设存在一个最优安排A不包含e1，并以ei开始，则易见：A-{ei}∪{e1}也是最优的活动安排；
依此类推: 若A是原问题的最优解，A’=A-{1}是活动安排E’={ei ∈E: si ≥f1}的最优解（为什么？）；
每次一步贪心选择把原问题简化为一个更小的与原问题具有相同形式的字问题。
贪心算法的基本要素
对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。
但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题;
贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。贪心选择可以依赖于以往的选择，但是决不依赖于将来所做的选择。

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
考察问题的一个最优解S（假设已经得到），按照贪心选择策略对最优解S做一个修改得到另外一个解S’；
证明新解S’ 和假设的最优解S 同一或者具有相同的最优值。

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
活动安排问题中的最优子结构性质表现：
若A是原问题E的包含活动1的一个最优解，A’=A-{1}是活动安排E’={ei ∈E: si ≥f1}的最优解。

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。
但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?
是否能用动态规划算法求解的问题也能用贪心算法求解?
??

0-1背包问题：
给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

背包问题：
与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

用贪心算法解背包问题的基本步骤：

首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。
若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。
依此策略一直地进行下去，直到背包装满为止。

算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为
O（nlogn）。当然，为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。
public static float knapsack(float c, float [] w, float [] v,float [] x)
{
int n=;
Element [] d = new Element [n];
fo