第六章貪心法

第六章貪心法第一頁，共四十八頁，2022年，8月28日第六章貪心法貪心法的學習提綱一般方法適合求解的問題基本思想(求解問題的過程)算法控制流程算法的正確性證明應用舉例背包問題帶時限的作業(yè)排序問題第二頁，共四十八頁，2022年，8月28日貪心算法的直觀含義

例1.如：找硬幣0.15元，要求硬幣數(shù)最少。找硬幣方法就是一種貪心算法.（1）面值；5分、2分、1分：（2）面值：11分、5分、1分：從此例可以看出：1，貪心法未必總能求得問題的最優(yōu)解；2，貪心算法總是作出在當前看來是最好的選擇.也就是說貪心算法不從整體最優(yōu)上加以考慮,它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。雖然貪心算法不是對所有問題都能得到整體最優(yōu)解,但對范圍相當廣的許多問題它都能產(chǎn)生最優(yōu)解。如單源最短路徑問題，最小生成樹問題等。而且,在一些情況下，即使貪心算法不能得到整體最優(yōu)解，但其最終結果卻是最優(yōu)解的很好的近似解！3個5分(最優(yōu))1個11分4個1分(次優(yōu))第三頁，共四十八頁，2022年，8月28日6.1一般方法貪心方法適合的問題是最優(yōu)化問題。最優(yōu)化問題：有n個輸入，而它的解就由這n個輸入的滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解。顯然，可行解一般來說是不唯一的，為了衡量可行解的好壞，問題還給出某個值函數(shù)，稱為目標函數(shù)，使目標函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。目標函數(shù)：約束條件（函數(shù)）：其中：可行解：如找硬幣問題可描述如下：

最優(yōu)化問題的解可表示成一個n元組X=（x1,x2…xn），其中每個分量取自某個值集S，所有允許的n-元組組成一個侯選解集。第四頁，共四十八頁，2022年，8月28日6.1一般方法貪心方法適合的問題是最優(yōu)化問題。最優(yōu)化問題：有n個輸入，而它的解就由這n個輸入的滿足某些事先給定的約束條件的某個子集組成，而把滿足約束條件的子集稱為該問題的可行解。顯然，可行解一般來說是不唯一的，為了衡量可行解的好壞，問題還給出某個值函數(shù)，稱為目標函數(shù)，使目標函數(shù)取極值(極大或極小)的可行解，稱為最優(yōu)解。最優(yōu)化問題的解是一個n元組貪心法是通過分步?jīng)Q策的方法來解決問題的。貪心法在求解問題的每一步上作出某種決策，產(chǎn)生n-元組的一個分量，貪心法要求根據(jù)題意，選定一種最優(yōu)量度標準，作為選擇當前分量的依據(jù)，這種在貪心法每一步上用做決策依據(jù)的選擇準則被稱為最優(yōu)量度標準（貪心準則，也稱貪心選擇性質(zhì)）。第五頁，共四十八頁，2022年，8月28日6.1一般方法貪心法的基本思想:

是依據(jù)題意選取一種量度標準，然后按照這種量度標準對這n個輸入進行排序，并按序一次輸入一個量，作為n-元組的一個分量，如果這個輸入量的加入不滿足約束條件,則不把此輸入加入到部分解向量中.貪心法求解問題的過程:選取最優(yōu)量度標準依最優(yōu)量度標準對n個輸入排序初始狀態(tài)下,解向量solution=φ中;按序一次取一個輸入量，作為n-元組的一個分量，若加入該分量滿足給定的約束條件，則加入，否則，不加入，繼續(xù)檢測下一個分量.

第六頁，共四十八頁，2022年，8月28日貪心方法的抽象化控制算法6.1貪心法的控制流程SolutionTypeGreedy(STypea[]，intn){SolutionTypesolutions=φ

//將解向量solution初始化為空／

for(inti=0;i<n;i++){STypex=Select(a);if(Feasiable(solution,x))solutions=UNION(solution,x);}returnsolution;}從算法6.1可看出，一旦能選擇出某個問題的最優(yōu)量度標準，那么用貪心方法求解這個問題則特別簡單有效。第七頁，共四十八頁，2022年，8月28日n個輸入按某種量度標準排序……按序一次選擇一個輸入量。滿足約束條件，加入解解不滿足約束條件，揚棄…..

對于一個給定的問題，往往可能有好幾種量度標準。用其中的大多數(shù)量度標準作貪心處理所得到該量度意義下的最優(yōu)解并不是問題的最優(yōu)解，而是次優(yōu)。

選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)量度標準是使用貪心法設計求解的核心問題。第八頁，共四十八頁，2022年，8月28日6.1一般方法貪心法小結:適合求解的問題:解為n-元組的最優(yōu)化問題;貪心法是分步?jīng)Q策,每一步?jīng)Q策產(chǎn)生n-元組的一個分量貪心法并不是從整體上考慮最佳，而是做當前看來是最佳的選擇，這種選擇依賴于以前的選擇，但不依賴于以后的選擇和子問題,故它的特征是自頂向下一步一步地做出貪心決策.自頂向下:是以迭代的方式作出相繼的貪心選擇,每一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題.第九頁，共四十八頁，2022年，8月28日1.最優(yōu)量度標準所謂貪心法的最優(yōu)量度標準,是指可以根據(jù)該量度標準，實行多步?jīng)Q策進行求解，雖然在該量度意義下所做的這些選擇都是局部最優(yōu)的，但最終得到的解卻是全局最優(yōu)的。因此，選擇最優(yōu)量度標準是使用貪心法求解問題的核心問題.6.2貪心法的基本要素當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時,稱此問題具有最優(yōu)子結構性質(zhì).問題的最優(yōu)子結構性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。2.最優(yōu)子結構性質(zhì)第十頁，共四十八頁，2022年，8月28日6.3背包問題0-1背包問題：給定n種物品和一個背包.物品i的重量是Wi,其價值為pi,背包的容量為C.應如何選擇裝入背包的物品,使得裝入背包中物品的總價值最大？在選擇裝入背包的物品時,對每種物品i只有2種選擇,即裝入背包或不裝入背包.背包問題:與0-1背包問題類似,所不同的是在選擇物品i裝入背包時,可以選擇物品i的一部分,而不一定要全部裝入背包,1≤i≤n。這2類問題都具有最優(yōu)子結構性質(zhì),極為相似,但背包問題可以用貪心法求解,而0-1背包問題卻不能用貪心法求解。第十一頁，共四十八頁，2022年，8月28日6.3背包問題已知有n種物品和一個可容納M重量的背包,每種物品i的重量為wi.假定將物品i的一部分xi放入背包就會得到pixi的效益,這里，0≤xi≤1，pi>0.如果這些物品重量的和大于M,要求所有選中要裝入背包的物品總重量不得超過M,而裝入背包物品獲得的總效益最大.即

0≤xi≤l，pi>0，wi>0，0≤i≤n-1滿足約束條件的任一集合(x0，…，xn-1)是一個可行解(即能裝下)，使目標函數(shù)取最大值的可行解是最優(yōu)解。背包問題描述：約束條件：第十二頁，共四十八頁，2022年，8月28日

例6.1n＝3，M=20，P＝(25，24，15)，W=(18，15，10)

假設物品可分，故有可行解無數(shù)個，其中的四個可行解是：

(x0，x1，x2)∑wixi∑pixi①(1/2，1/3，1/4) 16.5 24.25②(1，2/15，0) 20 28.2③(0，2/3，1) 20 31④(0，1，1/2) 20 31.5

在這四個可行解中，第④個解的效益值最大。但這個解是否是背包問題的最優(yōu)解，尚無法確定，但有一點是可以肯定的，即對于一般背包問題，其最優(yōu)解顯然必須裝滿背包。6.3背包問題第十三頁，共四十八頁，2022年，8月28日貪心法求解背包問題選擇量度標準計算在此量度標準下的”最優(yōu)解”(1)選目標函數(shù)作為量度標準,

即”效益”優(yōu)先,使每裝入一件物品就使背包獲得最大可能的效益值增量.按物品收益從大到小排序0,1,2解為:(x0,x1,x2)=(1,2/15,0)收益:25+24*2/15=28.26.3背包問題非最優(yōu)解原因:只考慮當前收益最大,而背包可用容量消耗過快.M=20,P＝(25,24,15)W=(18，15，10)第十四頁，共四十八頁，2022年，8月28日貪心法求解背包問題選擇量度標準計算在此量度標準下的”最優(yōu)解”(2)選重量作為量度,使背包容量盡可能慢地被消耗.6.3背包問題按物品重量從小到大排序:2,1,0;解為:

(x0,x1,x2)=(0,2/3,1)

收益:

15+24*2/3=31非最優(yōu)解原因:雖然容量消耗慢，但效益沒有很快的增加.M=20,P＝(25,24,15)W=(18，15，10)第十五頁，共四十八頁，2022年，8月28日貪心法求解背包問題選擇量度標準計算在此量度標準下的”最優(yōu)解”(3)選利潤/重量為量度

使每一次裝入的物品應使它占用的每一單位容量獲得當前最大的單位效益。6.3背包問題M=20,P＝(25,24,15)W=(18，15，10)按物品的pi/wi重量從大到小排序:1,2,0;解為:

(x0,x1,x2)=(0,1,1/2)

收益:

24+15/2=31.5可見，可以pi/wi

作為背包問題的最優(yōu)量度標準.最優(yōu)解第十六頁，共四十八頁，2022年，8月28日算法6.2以p[i]/w[i]為最優(yōu)量度標準的背包問題的貪心算法

voidGreedyKnapsack(float*p,float*w,floatM,intn,float*x){//前置條件：w[i]已按p[i]/w[i]的非增次序排列floatu=M;//u為背包剩余載重量，初始時為mfor(inti=0;i<n;i++)x[i]=0;//對解向量x初始化for(i=0;i<n;i++)//按最優(yōu)量度標準選擇解的分量{ if(w[i]>u)break; x[i]=1.0; u=uw[i];}if(i<n)x[i]=u/w[i];}

6.3背包問題（1）由此算法所得解的形式為:

(1,1,1,….,1,xj,0,…,0)（2）算法的正確性：貪心法得到的解是否是最優(yōu)解需要證明第十七頁，共四十八頁，2022年，8月28日定理6.1

如果p0/w0≥p1／w1≥…≥pn-1／wn-1，則算法GreedyKnapsack對于給定的背包問題實例生成一個最優(yōu)解。

證明:設X=(x0，…，xn-1)是GreedyKnapsack所生成的解.設j是使x(i)≠1的最小下標。由算法可知，有：(1,….,1,xj，0,…,0)j

（1）假設X不是最優(yōu)解，另有最優(yōu)解為Y=(y0，…，yn-1)，則定有∑piyi>∑pixi。不失一般性，可以假定∑wiyi=M。

（2）設k是使得yk≠xk的最小下標?？梢酝频脃k<xk。這可從三種可能發(fā)生的情況，即k<j，k＝j或k>j分別得證明：

①若k<j，(1,1,1,….,1,xj

,0,…,0)Kj因為yk≠xk，從而yk<xk。②若k＝j，(1,1,1,….,1,xj

,0,…,0)K=j若yk>xk，顯然有∑wiyi>M，從而yk<xk。

③若k>j，(1,1,1,….,1,xj

,0,…,0)jK反證法：所以,必有yk<xk若yk>xk，有∑wiyi>M，是不可能的。第十八頁，共四十八頁，2022年，8月28日(3)

把yk增加到xk,那末必須從(yk+1，…，yn-1)中減去同樣多的量，使得所用的總容量仍是M。這導致一個新的解Z=(z0，…，zn-1)，其中，zi=xi，0≤i≤k，并且

因此，對于Z有變換

Z不比Y差,重復上面的討論,把Y轉換成X,從而證明了X也是最優(yōu)解.證畢。第十九頁，共四十八頁，2022年，8月28日對于0/1背包問題，使用貪心法，并不一定能求得最優(yōu)解，因此，貪心法不能用來求解0/1背包問題例，n＝3，M=25，P＝(32，24，15)，W(16，15，10).P/W=(2,1.6,1.5)X=(0)∑p=32,CU=M-W(0)=9不能放下任何物品，顯然X=(0)不是最優(yōu)解。最優(yōu)解是(1,2)，利潤為39。6.3背包問題第二十頁，共四十八頁，2022年，8月28日6.3帶有限期的作業(yè)排序在一單機無其他資源約束的處理系統(tǒng)中，運行n個作業(yè)，假設每個作業(yè)運行1個單位時間，且每個作業(yè)i都有一個截止期限di>0(它是整數(shù))，若作業(yè)i能在它的期限截止前被完成，則可獲得pi>0的效益。要求找到作業(yè)的子集X及X的一個排列α，使得按α調(diào)度作業(yè)運行，X中的作業(yè)都能如期完成，且獲收益最大。

可行解：子集X中的作業(yè)都能如期完成，則X為可行解。

可行解的收益：可行解X中所有作業(yè)的收益之和，即。

最優(yōu)解：具有最大收益的可行解就是最優(yōu)解。6.3.1問題描述

第二十一頁，共四十八頁，2022年，8月28日例6.2n=4,(p0,p1,p2,p3)＝(100,10,15,20)、(d0,d1,d2,d3)=(2,1,2,1)

可行解和它們的效益值如下：可行解處理順序效益值①(0)1100②(1)110③(2)115(3)120(0，1)1，0110(0，2)0，2或2，0115(0，3)3，0120(1，2)1，225解⑦是最優(yōu)的,所允許的處理次序是:先處理作業(yè)3,再處理作業(yè)0.306.3帶有限期的作業(yè)排序第二十二頁，共四十八頁，2022年，8月28日6.3.2貪心法求解

(1),把目標函數(shù)作為量度.使用這一量度,下一個要計入的作業(yè)將是使得在滿足所產(chǎn)生的X是一個可行解的限制條件下讓得到最大增加的作業(yè).(2),按pi的非增次序來考慮這些作業(yè);如例6.2，按pi的非增次序對作業(yè)進行排序（0，3，2，1）開始時:

X＝φ，，X＝{0}，p0=100作業(yè)0有最大效益

X＝{0，3}p0+p3=120作業(yè)3有第二大效益作業(yè)2,1都被舍棄6.3帶有限期的作業(yè)排序第二十三頁，共四十八頁，2022年，8月28日算法6.3帶時限作業(yè)排序算法voidGreedyJob(int*d，int*X，n){

//作業(yè)按p0≥p1≥…≥pn-1的次序輸入，它們的期限值d(i)≥1，0≤i≤n-1，n≥1。X是在它們的截止期限前完成的作業(yè)的集合//

X←{0}for(inti=1;i<n;i++)

if(X∪{i}的所有作業(yè)都能在它們的截止期限前完成)

X=X∪{i}}6.3帶有限期的作業(yè)排序思考:1，該算法能否得到最優(yōu)解？2，如何變?yōu)橛行У乃惴ǎ?.3.2貪心法求解

第二十四頁，共四十八頁，2022年，8月28日定理6.2算法6.3所描述的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。

證明:設X=(x0,x1,…xk)是某個帶時限作業(yè)排序問題實例的貪心法求得的解，若X不是最優(yōu)解，假設另有Y=(y0,y1,…yr)是最優(yōu)解.(1)假設X≠Y,必有且若，則Y不是可行解；否則，Y是可行解，那么貪心算法會將屬于Y但不屬于X的其他作業(yè)繼續(xù)加入X。若，則Y不是最優(yōu)解；(2)存在排列α、β，使X、Y可行6.3帶有限期的作業(yè)排序6.3.3算法正確性---(1)該算法能否找到最優(yōu)解?第二十五頁，共四十八頁，2022年，8月28日(3)將α，β中的相同作業(yè)移到相同位置。

設x是既屬于X又屬于Y的一個作業(yè);又設x在α中在t到t+1時刻被調(diào)度,而在β中則在t’到t’+1時刻被調(diào)度.可以調(diào)換α或β中的作業(yè),使x在α和β中都在同一時刻被安排.如果t<t’，交換α中的x與y;t………………………………zxtxt’yt………………………………xytzt’x如果t>t’，交換β中的x與z;重復使用，可使α和β中都有的作業(yè)在相同的時刻被安排。6.3帶有限期的作業(yè)排序6.3.3算法正確性---(1)該算法能否找到最優(yōu)解?

第二十六頁，共四十八頁，2022年，8月28日(4)對于α和β中的不同作業(yè)，用α中的相同位置的作業(yè)替換β中的作業(yè)。

設，并且作業(yè)a是使得的一個收益最大的作業(yè)，那么，對于任意作業(yè)b，，都有pa≥pb。否則作業(yè)b被程序6-3加入X中。假定b是其中一個作業(yè)，它在β中的位置與a在α中的位置相同，用a取代β序列中的b，得到一個新序列Y’

，顯然Y’的效益值不小于Y的效益值，并且Y’比Y少一個與X不同的作業(yè)。重復使用上述的轉換，將使Y能在不減效益值的情況下轉換成X，因此X也必定是最優(yōu)解。證畢。t………………a………………bpa≥pb6.3帶有限期的作業(yè)排序第二十七頁，共四十八頁，2022年，8月28日6.3帶有限期的作業(yè)排序6.3.4可行性判定---(2)如何變?yōu)橛行惴?(1)檢查某種排列a是否可行?只需檢查作業(yè)aj是否滿足daj>=j+1∵每個作業(yè)執(zhí)行一個單位時間∴排列位置為j的作業(yè)aj應在j+1時刻執(zhí)行完畢(2)判斷X子集是否可行?只需判斷它的一個特殊排列是否可行即可;這個特殊的排列就是X中作業(yè)按時限的非降次序的排列

算法6-3的核心步驟是:判定集合X∪{i}中的作業(yè)是否能在截止期限前完成,這一操作步驟也就是所謂的可行性判定.

某一作業(yè)子集X是否是可行解，只需找到一種X的排列a,如果X中的作業(yè)能按a的次序執(zhí)行而不超期，則X為可行解.第二十八頁，共四十八頁，2022年，8月28日6.3帶有限期的作業(yè)排序6.3.4可行性判定---(2)如何變?yōu)橛行惴?

定理6-3

X=(x0,x1,…xk)是k個作業(yè)的集合,a=(a0,a1,a2…ak)是X的一種特定排列,它使得da0<=da1<=….dak,其中，daj是作業(yè)aj的時限.X是一個可行解當且僅當X中的作業(yè)能夠按a次序調(diào)度而不會有作業(yè)超期.證明:(1)””如果X中作業(yè)能夠按照a次序調(diào)度而不會有作業(yè)超期,則X是可行解.(2)”->”如果X是可行解，則必存在X的至少一種排列使得X中作業(yè)可以按該排列執(zhí)行而不會有超期，設β=(β0,β1,…βk),β≠α是這樣的排列.令i是使得αi≠βi的最小下標，那么作業(yè)αi的時限必然小于βi的時限,由于α和β是X中作業(yè)的兩種不同的排列,所以β中必定也包含作業(yè)αi,很顯然,αi在β中的位置比它在α中的位置靠后.將β中的αi與βi交換位置,不會引起作業(yè)超期.重復以上過程,最終將β變換成α,這就是說,按α次序調(diào)度作業(yè)不會出現(xiàn)超期,因此α是可行的調(diào)度方案第二十九頁，共四十八頁，2022年，8月28日帶時限的且每個作業(yè)運行單位時間的作業(yè)排序過程:(1),按收益非增次序對作業(yè)排序:p0≥p1≥…pn-1;(2),按作業(yè)收益從大到小考察作業(yè);初始時,x[0]=0,即X={x[0]};現(xiàn)在處理作業(yè)j,假設已處理了I-1個作業(yè),其中有k+1個作業(yè)已計入部分解向量X={x[0],x[1]…x[k]}之中,且有d[x[0]]≤d[x[1]]≤…≤d[x[k]]。∵部分解可行∴d[x[i]]≥i+1(0≤i≤k)為了判斷XU{j}是否可行,只需看能否找出按期限的非降次序插入作業(yè)j的適當位置r,使得作業(yè)j在此處插入后有d[X[r]]≥r+1,0≤r≤k.6.3帶有限期的作業(yè)排序6.3.5作業(yè)排序算法

………………kj第三十頁，共四十八頁，2022年，8月28日(3)判斷j是否允許添加到部分解向量X中將作業(yè)j按時限的非減次序插入向量X={x[0],x[1]…x[k]}中的某個位置，使得作業(yè)j插入后，由k+2個分量組成的部分解向量仍按時限的非減次序排列假設j被插入于下標r+1處,為了在r+1處插入j作業(yè)，x[r+1]…x[k]在向量中的位置都要依次后移一位，形成一個新的部分解向量.為了保證在添加作業(yè)j后的作業(yè)子集仍構成可行解，必須滿足:a,d[x[j]]>j+1(r+1≤j≤k)b,d[j]>r+1;6.3帶有限期的作業(yè)排序6.3.5作業(yè)排序算法

第三十一頁，共四十八頁，2022年，8月28日【程序6-4】帶時限的作業(yè)排序程序intJS(int*d,int*x,intn){//設p0≥p1≥…≥pn1intk=0;x[0]=0;for(intj=1;j<n;j++){intr=k;while(r>=0&&d[x[r]]>d[j]&&d[x[r]]>r+1)r--; if((r<0||d[x[r]]<=d[j])&&d[j]>r+1){ for(inti=k;i>=r+1;i--)x[i+1]=x[i]; x[r+1]=j;k++; }}returnk;}6.3帶有限期的作業(yè)排序6.3.5作業(yè)排序算法

n-1

//O(n)k+1k-r每次迭代的總時間為O(k),若s是k的終值,即s是最后所得解的作業(yè)數(shù).則JS所需的總時間是O(sn).由于s<=n,因此最壞時間是O(n2)(當di=n-i0≤i≤n-1時),所以最壞時間是:O(n2)復雜度分析：對于JS，其復雜度參數(shù)有兩個：即作業(yè)數(shù)n和包含在解中的作業(yè)數(shù)s.第三十二頁，共四十八頁，2022年，8月28日例n=4，P＝(100，20，15，10，)和d=(2,1,2,1)01.X[0]=0,k=02.j=1,r=k=0,∵

r>=0&&d[x[r]]=2>d[j]=1&&d[x[r]]>r+1

∴r=r-1=-1∵r=-1<0

&&

d[j]=1>r+1∴可以后移,且j可以插入r+1處103.j=2,r=k=1,d[x[r]]=2==d[j]且d[x[r]]==r+1不可以后移；又∵d[j]=r+1∴j不可以插入。4.j=3,r=k=1,d[x[r]]=2>d[j]=1但d[x[r]]=2==r+1∴不可以后移；又∵d[j]=1<r+1∴j不可以插入。X={1,0}6.3帶有限期的作業(yè)排序6.3.5作業(yè)排序算法

第三十三頁，共四十八頁，2022年，8月28日改進的可行解判定方法的主要思想是:令b=min{n,max{di|0≤i≤n-1}}b為可行的作業(yè)調(diào)度方案所需的最大時間,b不會超過作業(yè)的最大時限,也不會超過作業(yè)的總數(shù)n∵b是可行作業(yè)調(diào)度方案所需的最大時間;∴可將b分成b個時間片，每個時間片一個單位;為了實現(xiàn)算法方便，引入了虛擬時間片[-1,0],它不同用于時間分配作業(yè)排序過程:(1),設作業(yè)已按收益的非增次序排列(2),作業(yè)i的時限是di,為它分配的時間片是[r-1,r],其中，r是使0<r≤di的最大整數(shù)且[r-1,r]是空閑的

6.3帶有限期的作業(yè)排序6.3.6改進的作業(yè)排序算法

第三十四頁，共四十八頁，2022年，8月28日具體做法是:為收益最大的0作業(yè)分配時間片[d0-1,d0],為收益次大的作業(yè)1分配時間片時，首先考慮時間片[d1-1,d1],如果該時間片已分配,再考慮前一時間片[d1-2,d1-1],依次向前尋找第一個空閑的時間片分配之,如果d1之前的所有時間片均已分配，則作業(yè)1舍棄，原則:盡可能推遲對作業(yè)的處理。6.3帶有限期的作業(yè)排序6.3.6改進的作業(yè)排序算法

例6-3n=5(d0,d1,d2,d3,d4)=(2,2,1,3,3)(p0,p1,p2,p3,p4)=(20,15,10,5,1)解：

b=min{5，3}=3

-101234103第三十五頁，共四十八頁，2022年，8月28日貪心法--------總結與作業(yè)總結與作業(yè)總結：（1）適合求解的問題---解為n-元組的最優(yōu)化問題問題應該具備的特征是:具有最優(yōu)量度標準

具有最優(yōu)子結構特性（2）貪心法的特征:自頂向下,多步?jīng)Q策,每次產(chǎn)生n-元組的一個分量,貪心法當前的選擇可能依賴于已經(jīng)做出的選擇,但不依賴于尚未作出的選擇和子問題（3）貪心法求解問題的過程：選擇最優(yōu)量度標準依最優(yōu)量度標準對輸入排序依最優(yōu)量度標準選擇輸入產(chǎn)生解向量中的一個分量算法的正確性證明第三十六頁，共四十八頁，2022年，8月28日貪心法--------總結與作業(yè)總結與作業(yè)P132：6-1，6-2,6-3,6-17作業(yè)：思考：P133：6-4第三十七頁，共四十八頁，2022年，8月28日定理6-3提供了一種高效的可行解的判定方法。使得在按最優(yōu)量度標準，即按作業(yè)收益的非增次序選擇下一個作業(yè)后，可以有效地判定是否可將該作業(yè)加入已生成的部分解向量X中，具體判定方法是：對任意一個部分解作業(yè)子集X=(x0,x1,…xk)，使X中的作業(yè)按期限的非降次序排列，設a=(a0,a1,a2…ak)，da0≤da1≤…≤dak是X的這樣的排列,為了判定a是否可行，只需對每個作業(yè)aj判斷daj》=j+1是否成立。作業(yè)i能否加入X的充要條件是，作業(yè)i能否加入這個序列?！璳i6.3帶有限期的作業(yè)排序6.3.5作業(yè)排序算法

第三十八頁，共四十八頁，2022年，8月28日

假設已處理了I-1個作業(yè),其中有k個作業(yè)已計人X(0),X(1),…,X(k)之中,且有D(X(1))≤D(X(2))≤…≤D(X(k)),現(xiàn)在處理作業(yè)i.為了判斷XU{i}是否可行,只需看能否找出按期限的非降次序插入作業(yè)i的適當位置r,使得作業(yè)i在此處插入后有D(X(r))≥r,1≤r≤k+1.………………kirD(X(r))≤D(i),作業(yè)i應該放在r+1處D(i)〉r，作業(yè)i可以放在r+1處，從r+1到k的作業(yè)應向后移動。6.3帶有限期的作業(yè)排序第三十九頁，共四十八頁，2022年，8月28日找作業(yè)i可能的插入位置可如下進行:將D(X(k))，D(X(k一1))，…，D(X(1))逐個與D(i)比較，直到找到位置r,它使得D(X(r))≤D(i)，只要D(i)>r,就可將作業(yè)I在位置r+1處插入,從而得到一個按期限的非降次序排列的含有k+1個作業(yè)的可行解。以上過程可反復進行到對第n個作業(yè)處理完畢,所得到的貪心解是一個最優(yōu)解。這一處理過程可用算法6.3來描述.算法中引進了一個虛構的作業(yè)0,它放在X(0),且D(X(0))＝0.引入這一虛構作業(yè)是為了便于將作業(yè)插入位置1。6.3帶有限期的作業(yè)排序第四十頁，共四十八頁，2022年，8月28日1.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。6.2貪心法的基本要素第四十一頁，共四十八頁，2022年，8月28日當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時,稱此問題具有最優(yōu)子結構性質(zhì).問題的最優(yōu)子結構性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。2.最優(yōu)子結構性質(zhì)6.2貪心法的基本要素3.貪心法與動態(tài)規(guī)劃法的異同共同點:都可用來求解最優(yōu)化問題;且要求問題具有最優(yōu)子結構性質(zhì).差異:貪心法是自頂向下的決策方法,而動態(tài)規(guī)劃法使用自底向上的決策方法.對于具有最優(yōu)子結構的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?當具有最優(yōu)子結構特性的最優(yōu)化問題找不到最優(yōu)量度標準時，可以選用動態(tài)規(guī)劃方法.第四十二頁，共四十八頁，2022年，8月28日定理6.2算法6.3所描述的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。

證明:設X=(x0,x1,…xk)是某個帶時限作業(yè)排序問題實例的貪心法求得的解，若X不是最優(yōu)解，假設另有Y=(y0,y1,…yr)是最優(yōu)解.(1)假設X≠Y,必有且(2)存在排列a,b使X,Y可行(3)將a,b中的相同作業(yè)移到相同位置(4)對于不同作業(yè)用X中的相同位置上的作業(yè)替換Y的作業(yè)假定I≠X,因此,至少存在著這樣的兩個作業(yè)a和b,使且,b∈Y且.由貪心方法可以得出,對于在Y中又不在X中的所有作業(yè)b,都有pa≥pb.這是因為若pb>pa,則貪心方法會先于作業(yè)a考慮作業(yè)b并且把b計入到X中去.

t………………a………………bpa≥pb6.3帶有限期的作業(yè)排序第四十三頁，共四十八頁，2022年，8月28日證明:設X=(x0,x1…xk)是某個帶時限作業(yè)排序問題實例的貪心算法求得的解，如果X不是最優(yōu)解，另有Y=(y0,y1,…yr)是最優(yōu)解.設X≠Y,則必有因為若則Y不是可行解;否則，若Y是可行解，那么貪心算法定會將屬于Y但不屬于X的其他作業(yè)繼續(xù)加入X,若則Ｙ不是最優(yōu)解。因為Ｘ和Ｙ是問題的兩個可行解，設分別是X和Y的可行的作業(yè)排列,也就是說,按的次序調(diào)度作業(yè)執(zhí)行，X和Y中的作業(yè)都不會超期.將中相同的作業(yè)移到相同的位置,并且不影響兩個排列的可行解性質(zhì).若存在作業(yè)x,使得,x在序列中的位置先于在中的位置可將a序列中的x和z交換位置，這樣不會引起任何作業(yè)超期.定理6.2程序6-3的貪心方法對于作業(yè)排序問題總是得到一個最優(yōu)解。6.3.3算法正確性---(1)該算法能否找到最優(yōu)解?………………………………yxtxzt’x與z交換前………………………………yztxxt’x與z交換后第四十四頁，共四十八頁，2022年，8月28日因為,則必存在兩個作業(yè)a和b,使得假定作業(yè)a是使得的一個收益最大的作業(yè)，那么，由貪心法可知，對任意作業(yè)b,都有pa≥pb,否則，作業(yè)b將被程序6-3加入X中，假定b是其中一作業(yè)，它在中的位置與a