第3章贪心算法贪心算法的直观含义3.1一般方法贪心方法的抽象化控制n个输入按某种量度标准排序3.2背包问题例3.1n＝3，M=20，P＝(25，24，15)，W(18，15，10)。其中的四个可行解是：(x1，x2，x3)∑wixi∑pixi①(1/2，1/3，1/4)16．524．25②(1，2/15，0)2028．2③(0，2/3，1)2031④(0，1，1/2)2031．5在这四个可行解中，第④个解的效益值最大。这个解是背包问题在这一情况下的最优解。例，n＝3，M=25，P＝(25，24，15)，W(18，15，10)。X=(1)∑p=25,CU=M-W(1)=7不能放下任何物品，显然X=(1)不是最优解。最优解是(2,3)，利润为39。贪心策略与最优量度表算法3.2背包问题的贪心算法procedureKNAPSACK(P，W，M，X，n)//P(1：n)和W(1；n)分别含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1：n)是解向量//realP(1：n)，W(1：n)，X(1：n)，M，cu；integeri，n；X←0//将解向量初始化为零//cu←M//cu是背包剩余容量//fori←1tondoifW(i)>cuthenexitendifX(i)←1cu←cu-W(i)repeatifi≤nthenX(i)←cu/W(i)endifendGREEDY-KNAPSACK定理3.1如果p1/w1≥p2／w2≥…≥pn／wn，则算法KNAPSACK对于给定的背包问题实例生成一个最优解。现在，假定把yk增加到xk，那末必须从(yk+1，…，yn)中减去同样多的量，使得所用的总容量仍是M。这导致一个新的解Z=(z1，…，zn)，其中，zi=xi，1≤i≤k，并且3.3带有限期的作业排序例3.2的可行解和它们的效益值如下：可行解处理顺序效益值①(1)1100②(2)110③(3)115(4)120(1，2)2，1110(1，3)1，3或3，1115(1，4)4，1120(2，3)2，325解⑦是最优的，所允许的处理次序是：先处理作业4，再处理作业1。选择下一个作业的量度标准算法3.3作业排序算法的概略描述定理3.2算法3.3所描述的贪心方法对于作业排序问题总是得到一个最优解。现在，设SJ和SI分别是J和I的可行调度表。设i是既属于J又属于I的一个作业；又设i在SJ中在t到t+1时刻被调度，而在SI中则在t’到t’+1时刻被调度。可以调换SJ或SI中的作业，使i在SJ和SI中都在同一时刻被安排。如果t<t’，交换SJ中的i与j;下面考虑SJ与SI中的不同作业a,b，设a在[ta，ta+1]时刻被安排，设作业b在SI中的这一时刻被调度。根据对a的选择，pa≥pb。在SI去掉作业b而去调度作业a，这就给出了一张关于作业集合I’=I一{b}∪{a}可行的调度表。显然I’的效益值不小于I的效益值，并且I’比I少一个与J不同的作业。重复使用上述的转换，将使I能在不减效益值的情况下转换成J，因此J也必定是最优解。证毕。下面对算法3.3的第3条语句进一步细化。ifJ∪{i}的所有作业都能在它们的截止期限前完成thenJ←J∪{i}实现语句3，一个明显的方法是检验J中作业的所有可能的排列，假定J中有k个作业，这就需要检查k!个排列。事实上，对于J的可行性可以通过只检验J中作业的一种特殊的排列来确定，这个排列是按期限的非降次序来完成的。即将J中的K个作业按di1≤di2≤…≤dik排列，作业i能否加入J的充要条件是，作业i能否加入这个序列。假设已处理了I-1个作业，其中有k个作业已计人J(1)，J(2)，…，J(k)之中，且有D(J(1))≤D(J(2))≤…≤D(J(k))，现在处理作业i。为了判断JU{i}是否可行，只需看能否找出按期限的非降次序插入作业i的适当位置r，使得作业i在此处插入后有D(J(r))≥r，1≤r≤k+1。找作业i可能的插入位置可如下进行：将D(J(k))，D(J(k一1))，…，D(J(1))逐个与D(i)比较，直到找到位置r，它使得D(J(r))≤D(i)，只要D(i)>r，就可将作业I在位置r+1处插入，从而得到一个按期限的非降次序排列的含有k+1个作业的可行解。以上过程可反复进行到对第n个作业处理完毕，所得到的贪心解是一个最优解。这一处理过程可用算法3.3来描述。算法中引进了一个虚构的作业0，它放在J(0)，且D(J(0))＝0。引入这一虚构作业是为了便于将作业插入位置1。算法3.4带有限期和效益的单位时间的作业