8贪心策略.ppt

贪心策略
2
贪婪技术(Greedy Technique)
教学内容
背包问题的贪婪策略(Knapsack Problem)
Prim算法
Kruskal算法
Dijkstra算法
哈夫曼树(Huffman Trees)
要求
掌握贪婪技术的原理、效率分析方法,以及在常见问题问题中的应用。
贪心方法的基本思想
贪心是一种解题策略,也是一种解题思想
使用贪心方法需要注意局部最优与全局最优的关系,选择当前状态的局部最优并不一定能推导出问题的全局最优
利用贪心策略解题,需要解决两个问题:
该题是否适合于用贪心策略求解
如何选择贪心标准,以得到问题的最优/较优解
引例
在N行M列的正整数矩阵中,要求从每行中选出1个数,使得选出的总共N个数的和最大。

分析:要使总和最大,则每个数要尽可能大,自然应该选每行中最大的那个数。因此,我们设计出如下算法:
读入N, M,矩阵数据;
Total := 0;
for I := 1 to N do begin {对N行进行选择}
选择第I行最大的数,记为K;
Total := Total + K;
end;
输出最大总和Total;
5
部分背包问题(Knapsack Problem)
问题描述
已知有n种物品和一个可容纳W重量的背包,每种物品I的重量为wi,假定将物品I的某一部分xi放入背包就会得到pixi的效益(0≤xi≤1, pi>0) ,采用怎样的装包方法才会使装入背包物品的总效益为最大呢?
问题的形式描述
极大化 ∑ pixi
约束条件∑ wi xi ≤W
0≤xi≤1, pi>0, wi>0, 1≤i≤n
1≤i≤n
1≤i≤n
6
背包问题(Knapsack Problem)
方案1:按物品价值降序装包
方案2:按物品重量升序装包
方案3:按物品价值与重量比值的降序装包
例1 部分背包问题
给定一个最大载重量为M的卡车和N种食品,有食盐,白糖,大米等。已知第i种食品的最多拥有Wi公斤,其商品价值为Vi元/公斤,编程确定一个装货方案,使得装入卡车中的所有物品总价值最大。
分析:
因为每一个物品都可以分割成单位块,单位块的利益越大显然总收益越大,所以它局部最优满足全局最优,可以用贪心法解答,方法如下:先将单位块收益按从大到小进行排列,然后用循环从单位块收益最大的取起,直到不能取为止便得到了最优解。
算法
问题初始化; {读入数据}
按Vi从大到小将商品排序;
I := 1;
repeat
if M = 0 then Break; {如果卡车满载则跳出循环}
M := M - Wi;
if M >= 0 then 将第I种商品全部装入卡车
else
将(M + Wi)重量的物品I装入卡车;
I := I + 1; {选择下一种商品}
until (M <= 0) OR (I >= N)
10
贪婪技术(Greedy Technique)
A(1)
A(2)
…
A(n-1)
A(n)
某一问题的n个输入
B1(1)
B1(2)
…
B1(m)
该问题的一种解(可行解)
是A的一
个子集
满足一定
的条件
约束条件
Bk(1)
Bk(2)
…
Bk(m)
…
目标函数
取极值
最优解