谈贪心算法

谈谈贪心算法

例1.背包问题 【题目描述】

这是一大家很熟悉的背包问题。给定n种货物和一个载重量为m的背包。已知第i种货物的重量为wi ,其总价值为pi，编程确定一个装货方案，使得装入背包中货物的总价值最大。输出此总价值和装货方案。 【算法分析】

0，1背包问题对每种物品只有两种选择：选和不选，可用动态规划解决。而背包问题，可以选择物品的一部分装载，这样就可以把背包装满，用贪心算法可求得最优解。采用贪心标准是：选择单位重量价值高的货物优先装入，这样才能保证背包中所装货物总价值最大。而0，1背包用贪心算法却不能得到整体最优，为什么呢？我们来看一个例子：

有一背包容量为50千克，有三种货物：

物品1重10千克；价值60元； 物品2重20千克，价值100元； 物品3重30千克；价值120元。

1

20 20 10 总价值：（用贪心算法） 80+100+60=240

对于0，1背包问题，贪心选择之所以不能得到最

优解是因为它无法保证最终将背包装满，部分背包的 闲置使单位重量背包空间的价值降低。

例2．排队问题

【题目描述】

在一个医院B 超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0

输入数据：第1行一个正整数n（你<=10000》，第2行有n

2

个不超过 1000的正整数ti.

输出要求：n个人排队时间最小总和。 输入输出样例 输入：4 5 10 8 7 输出： 67

【算法分析】

本题贪心算法：n个人时间从小到大排序，就是这n个人最佳排队方案。求部分和的和即为所求。

反证法证明：假设有最优解序列：s1,s2…sn,如s1不是最小的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的人无影响，对sk之前的人等待都减少了，(s1-sk)>0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。

例3．:数列极差问题 【题目描述】

在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到

3

的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。

编程任务：对于给定的数列，编程计算出极差M。 输入输出样例：

输入： 4 2 1 4 3 输出： 13 【算法分析】

当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。

下面我们以求max为例来讨论此题用贪心策略求解的合理性。

讨论：假设经（Ｎ－3）次变换后得到３个数：a ,b , max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为 z1，z2，则有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换

4