貪心策略引例【問題描述】：在N行M列的正整數矩陣中,要求從每行中選出1個數,使得選出的總共N個數的和最大。

【試題分析】：本題可用貪心策略：選n次,每一次選相應行中的最大值即可。讀入n,m,矩陣數據；total=0;for(i=1;i<=n;i++)//對n行進行選擇{選擇第i行最大的數,記為k；total+=k；}輸出最大總和total；貪心算法貪心的定義：指從問題的初始狀態出發，向給定的目標推進。但不同的是，推進的每一步不是依據某一固定的遞推式，而是作一個當時看似最佳的貪心策略，不斷地將問題實例歸納為更小的相似的子問題，并期望通過所做的局部最優選擇產生出一個全局最優解。重點：貪心策略的選取。貪心與遞推的區別是：推進的每一步不是依據一個固定的遞推式,而是做一個當時看似最優的貪心選擇。鼠目寸光引例2：在一個N×M的方格陣中,每一格子賦予一個數（即為權）。規定每次移動時只能向上或向右。現試找出一條路徑,使其從左下角至右上角所經過的權之和最大。【分析】本題用貪心策略不能得到最優解,我們以2×4的矩陣為例。若按貪心策略求解,所得路徑為：1,3,4,6；若按動態規劃法求解,所得路徑為：1,2,10,6。貪心是一種解題策略,也是一種解題思想使用貪心方法需要注意局部最優與全局最優的關系,選擇當前狀態的局部最優并不一定能推導出問題的全局最優幾個簡單的貪心問題

【最優裝載問題】：給n個物體,第i個物體重量為wi,選擇盡量多的物體,使得總重量不超過C;【部分背包問題】:有n個物體,第i個物體的重量為wi,價值為vi,在總重量不超過C的情況下讓總價值盡量高;【乘船問題】:有n個人,第i個人重量為wi.每艘船的載重量為C,最多乘兩個人.用最少的船裝載所有人;貪心策略:最優裝載問題:先拿輕的貪心策略:部分背包問題:先拿性價比高的貪心策略:乘船問題:最輕的人和盡量重的人配對;應用舉例1---部分背包問題【問題描述】：給定一個最大載重量為M的卡車和N種食品,有食鹽,白糖,大米等。已知第i種食品最多擁有Wi公斤,其商品價值為Vi元/公斤,編程確定一個裝貨方案,使得裝入卡車中的所有物品總價值最大。【試題分析】：因為每一個物品都可以分割成單位塊,單位塊的利益越大顯然總收益越大,所以它局部最優滿足全局最優,可以用貪心法解答,方法如下：先將單位塊收益按從大到小進行排列,然后用循環從單位塊收益最大的取起,直到不能取為止便得到了最優解。問題初始化；//讀入數據按vi從大到小將商品排序；i=1;While(m>=0&&i<=n){if(m=0)return;//如果卡車滿載則跳出循環m=m-wi;if(m>=0)將第i種商品全部裝入卡車；else將m+wi重量的物品i裝入卡車;i=i+1;//選擇下一種商品}程序框架結構貪心策略求解的問題因此,利用貪心策略解題,需要解決兩個問題：首先,確定問題是否能用貪心策略求解；一般來說,適用于貪心策略求解的問題具有以下特點：1.可通過局部的貪心選擇來達到問題的全局最優解。運用貪心策略解題,一般來說需要一步步的進行多次的貪心選擇。在經過一次貪心選擇之后,原問題將變成一個相似的,但規模更小的問題,而后的每一步都是當前看似最佳的選擇,且每一個選擇都僅做一次。2.原問題的最優解包含子問題的最優解,即問題具有最優子結構的性質。在背包問題中,第一次選擇單位質量最大的貨物,它是第一個子問題的最優解,第二次選擇剩下的貨物中單位重量價值最大的貨物,同樣是第二個子問題的最優解,依次類推。其次,如何選擇一個貪心標準？正確的貪心標準可以得到問題的最優解,在確定采用貪心策略解決問題時,不能隨意的判斷貪心標準是否正確,尤其不要被表面上看似正確的貪心標準所迷惑。在得出貪心標準之后應給予嚴格的數學證明。應用舉例2---刪數問題【問題描述】：鍵盤輸入一個高精度的正整數n（n<=240位）,去掉其中任意s個數字后剩下的數字按照原來的次序將組成一個新的正整數。編程對給定的n和s,尋求一種方案,使得剩下組成的新數最小。輸入：1785464輸出：14貪心策略：每一步總是選擇一個使剩下的數最小的數字刪去，即按高位到低位的順序搜索，若各位數字遞增，則輸出最后一個數字；否則刪除第一個遞減區間的首字符，這樣刪一位便形成了一個新數字串。然后回到串首，按上述規則再刪下一個數字。重復上述過程s次為止，剩下的數字便是問題的解。N=178546=17546=1546=146=14cin>>s>>m;n=s.length();for(i=0;i<m;i++){for(j=0;j<n-1;j++)if(s[j]>s[j+1])//刪除第一個遞減區間的首字符 { for(k=j;k<n-1;k++)s[k]=s[k+1]; break; }n--;//否則刪除遞增區間的最后一個元素}i=0;while(s[i]==‘0’)i++;//去掉前面的0for(j=i;j<n;j++)cout<<s[j];應用舉例3---紀念品分組2005

Description：元旦快到了，校學生會讓樂樂負責新年晚會的紀念品發放工作。為使得參加晚會的同學所獲得的紀念品價值相對均衡，他要把購來的紀念品根據價格進行分組，但每組最多只能包括兩件紀念品，并且每組紀念品的價格之和不能超過一個給定的整數。為了保證在盡量短的時間內發完所有紀念品，樂樂希望分組的數目最少。

你的任務是寫一個程序，找出所有分組方案中分組數最少的一種，輸出最少的分組數目。Input：輸入文件group.in包含n+2行:

第1行包括一個整數w，為每組紀念品價格之和的上限，第2行為一個整數n，表示購來的紀念品的總件數G

第3-n+2行每行包含一個正整數Pi(5<=Pi<=w)w表示所對應紀念品的價格。Output：輸出文件group.out僅一行，包含一個整數，為最少的分組數目和。應用舉例3---紀念品分組2005

SampleInput1009902020305060708090SampleOutput：6

方法一：用快排【思想】貪心，排序，2個指針掃描最小和最大配，可以的i+1,j-1，不行j-1，直到i>j；

voidsolve(){inti=1,j=n,pair=0;while(i<j){if(a[i]+a[j]<=w){i++;j--;}elsej--;pair++;}if(i==j)pair++;cout<<pair<<endl;}方法二：用桶排序intmax,n,p,a[201]={0},t=0,i,j;cin>>max>>n;for(i=1;i<=n;i++){cin>>p;a[p]++;}//桶排序for(i=max;i>=1;i--)//分組while(a[i]){a[i]--;t++;for(j=max-i;j>0;j--)if(a[j]){a[j]--;break;}}cout<<t<<endl;應用舉例4---排隊打水問題【問題描述】：有N個人排隊到R個水龍頭去打水,他們裝滿水桶的時間為T1,T2,…,Tn為整數且各不相等,應如何安排他們的打水順序才能使他們花費的時間最少？【分析】：由于排隊時,越靠前面的計算的次數越多,顯然越小的排在越前面得出的結果越小(可以用數學方法簡單證明),所以這道題可以用貪心法解答,基本步驟：1.將輸入的時間按從小到大排序；2.將排序后的時間按順序依次放入每個水龍頭的隊列中；3.統計，輸出答案。應用舉例5---取數游戲2341

Description：給出2n(n<=100)個自然數(小于等于30000)。將這n個自然數排成一列，游戲雙方A和B從中取數，只允許從兩端取數。A先取，然后雙方輪流取數。取完時，誰取得數字總和最大為取勝方；若雙方和相等，屬B勝。試問A方是否有必勝策略？Input：兩行，第一行一個整數n；第二行有2*n個自然數。Output：第一行：若A有必勝策略，則輸出'yes'，否則輸出'no'SampleInput479364253SampleOutput：yes方法與技巧

運用貪心策略解題時，有的題目有不止一種可能的貪心標準，但不一定每種貪心標準都能夠得到正確的結果。因此，在運用貪心法時，一定要仔細分析，選擇恰當的貪心標準。應用舉例6---混合牛奶1648

Description牛奶包裝是一個如此低利潤的生意,所以盡可能低的控制初級產品(牛奶)的價格變的十分重要。請幫助快樂的牛奶制造者(merrymilkmakers)以可能的最廉價的方式取得他們所需的牛奶。快樂的牛奶制造公司從一些農民那購買牛奶，每個農民賣給牛奶制造公司的價格不一定相同。而且,如一只母牛一天只能生產一定量的牛奶,農民每一天只有一定量的牛奶可以賣。每天,快樂的牛奶制造者從每個農民那購買一定量的牛奶,少于或等于農民所能提供的最大值。

給出快樂牛奶制造者的每日的牛奶需求,連同每個農民的可提供的牛奶量和每加侖的價格,請計算快樂的牛奶制造者所要付出錢的最小值。注意:每天農民生產的牛奶的總數對快樂的牛奶制造者來說足夠的。Input第1行:二個整數,n和m。

第一個數值,n,(0<=n<=2,000,000)是快樂的牛奶制造者的一天需要牛奶的數量。

第二個數值,m,(0<=m<=5,000)是他們可能從農民那買到的數目。

第2到m+1行:每行二個整數,pi和ai。

pi(0<=pi<=1,000)是農民i牛奶的價格。

ai(0<=ai<=2,000,000)是農民i一天能賣給快樂的牛奶制造者的牛奶數量。Output：單獨的一行包含單獨的一個整數，表示快樂的牛奶制造者拿到所需的牛奶所要的最小費用

應用舉例7---數列極差問題1647

Description：在黑板上寫了N個正整數組成的一個數列，進行如下操作：每次擦去其中的兩個數a和b，然后在數列中加入一個數a×b＋1，如此下去直至黑板上剩下一個數，在所有按這種操作方式最后得到的數中，最大的為max，最小的為min，則該數列的極差定義為M＝max－min。

請你編程，對于給定的數列，計算極差。Input：第一個數N表示正整數序列長度（0＜＝N＜＝50000），隨后是N個正整數。N為0表示輸入結束。Output：計算極差SampleInput31230SampleOutput：2

應用舉例7---均分紙牌[問題描述]有N堆紙牌，編號分別為1，2，…,N。每堆上有若干張，但紙牌總數必為N的倍數。可以在任一堆上取若干張紙牌，然后移動。

移牌規則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。

現在要求找出一種移動方法，用最少的移動次數使每堆上紙牌數都一樣多。

例如N=4，4堆紙牌數分別為：

①9②8③17④6

移動3次可達到目的：

從③取4張牌放到④（981310）->從③取3張牌放到②（9111010）->從②取1張牌放到①（10101010）。[輸入]：N（N堆紙牌，1<=N<=100）

A1A2…An（N堆紙牌，每堆紙牌初始數，l<=Ai<=10000）[輸出]：所有堆均達到相等時的最少移動次數。‘[輸入輸出樣例]

4

98176

屏慕顯示：3應用舉例8---均分紙牌【試題分析】我們要使移動次數最少，就是要把浪費降至零。通過對具體情況的分析，可以看出在某相鄰的兩堆之間移動兩次或兩次以上，是一種浪費，因為我們可以把它們合并為一次或零次。因此，我們將相鄰兩堆間的移動次數限定在一次或零次。應用舉例7---均分紙牌【分析】如果你想到把每堆牌的張數減去平均張數，題目就變成移動正數，加到負數中，使大家都變成0，那就意味著成功了一半！拿例題來說，平均張數為10,原張數9，8，17，6，變為-1，-2，7，-4，其中沒有為0的數，我們從左邊出發：要使第1堆的牌數-1變為0，只須將-1張牌移到它的右邊（第2堆）-2中；結果是-1變為0，-2變為-3，各堆牌張數變為0，-3，7，-4；同理：要使第2堆變為0，只需將-3移到它的右邊（第3堆）中去，各堆牌張數變為0，0，4，-4；要使第3堆變為0，只需將第3堆中的4移到它的右邊（第4堆）中去，結果為0，0，0，0，完成任務。每移動1次牌，步數加1。也許你要問，負數張牌怎么移，不違反題意嗎？其實從第i堆移動-m張牌到第i+1堆，等價于從第i+1堆移動m張牌到第i堆，步數是一樣的。如果張數中本來就有為0的，怎么辦呢？如0，-1，-5，6，還是從左算起（從右算起也完全一樣），第1堆是0，無需移牌，余下與上相同；再比如-1，-2，3，10，-4，-6，從左算起，第1次移動的結果為0，-3，3，10，-4，-6；第2次移動的結果為0，0，0，10，-4，-6，現在第3堆已經變為0了，可節省1步，余下繼續。貪心的經典應用一、不相交的區間選擇?給n個開區間[Si,Fi],選擇盡量多的區間,使得兩兩不交。?算法:首先按照結束時間f1<=f2<…<=fn的順序排序,依次考慮各個活動,如果沒有和已經選擇的活動沖突,就選;否則就不選。?正確性:如果不選f1,假設第一個選擇的是fi,則如果fi和f1不交叉則多選一個f1更劃算;如果交叉則把fi換成f1不影響后續選擇。【培訓試題】活動選擇1649

Description學校在最近幾天有n個活動，這些活動都需要使用學校的大禮堂，在同一時間，禮堂只能被一個活動使。由于有些活動時間上有沖突，學校辦公室人員只好讓一些活動放棄使用禮堂而使用其他教室。

現在給出n個活動使用禮堂的起始時間Bi和結束時間Ei(Bi<Ei)，請你幫助辦公室人員安排一些活動來使用禮堂，要求安排的活動盡量多。Input第一行一個整數n(n<=1000)；

接下來的n行，每行兩個整數，第一個Bi，第二個是Ei(Bi<Ei<=32767)Output：輸出最多能安排的活動個數。SampleInput113514121481206811610573859213SampleOutput：4二、區間選點?給n個閉區間[ai,bi],在數軸上選盡量少的點,使每個區間內至少有一個點。分析：如果可以按照所有區間的結束位置排序,結束位置相同的項,開始位置小的項在前面。從區間1到區間n進行循環,對于當前區間,若集合中的數不能覆蓋它,則從區間末尾向前掃描,若當前數沒在集合中出現,則將該數加入集合,直至使集合能覆蓋該區間為止。【培訓試題】整數區間1650

Description：一個整數區間[A,B],A

請編程完成以下任務：

1.從文件中讀取區間的個數及其它們的描述；

2.找到滿足下述條件的所含元素個數最少的集合中元素的個數,對于每一個區間,都至少有兩個不同的整數屬于該集合。Input：首行包括區間的數目n,1<=n<=10000,接下來的n行,每行包括兩個整數a,b,被一空格隔開,0<=a<=b<=10000,它們是某一個區間的開始值和結束值。Output：第一行集合元素的個數,對于每一個區間都至少有兩個不同的整數屬于該區間,且集合所包含元素數目最少。SampleInput：436240247SampleOutput:4三、區間覆蓋?給n個閉區間[ai,bi],選擇盡量少的區間覆蓋一個給定線段[s,f]。?算法:對于每個區間,刪除在[s,f]之外的部分,并按a1<=a2<…<=an的順序排序,a相同時按b從大到小排序.從左到右掃描,如果當前區間可以覆蓋新的部分,選擇此線段。【培訓試題】線段覆蓋1893

Description:給出數軸上N條線段,第i條線段用兩個數表示Ai,Bi(Ai<Bi),表示從Ai到Bi的一條線段。現在請求出它們覆蓋數軸上的多長距離(Ai、Bi的絕對值可能達到10^9)。Input:第一行：N,以后N行，每行兩個數：AiBiOutput:一個數，表示覆蓋長度SampleInput328-11510SampleOutput：10

四、流水作業調度?n個作業要在由兩臺機器M1和M2組成的流水線上完成加工.每個作業i必須先在M1上然后在M2上加工,時間分別為ai和bi；?確定這n個作業的加工順序,使得從第一個任務開始在M1上加工到最后一個任務在M2上加工完成的總時間盡量小；?直觀上,最優調度一定讓M1沒有空閑,M2的空閑時間盡量少；?Johnson算法.設N1為a<b的作業集合,N2為a>=b的作業集合,將N1的作業按a非減序排序,N2中的作業按照b非增序排序,則N1作業接N2作業構成最優順序.?程序易于實現,時間O(nlogn),關鍵在于正確性證明。例：加工生產調度【問題描述】：某工廠收到了n個產品的訂單,這n個產品分別在A、B兩個車間加工,并且必須先在A車間加工后才可以到B車間加工。某個產品i在A、B兩車間加工的時間分別為Ai、Bi。怎樣安排這n個產品的加工順序,才能使總的加工時間最短。這里所說的加工時間是指：從開始加工第一個產品到最后所有的產品都已在A、B兩車間加工完畢的時間。【輸入】：第一行僅—個數據n(0<n<1000),表示產品的數量。接下來n個數據是表示這n個產品在A車間加工各自所要的時間(都是整數)。最后的n個數據是表示這n個產品在B車間加工各自所要的時間(都是整數)。【輸出】：第一行一個數據,表示最少的加工時間；第二行是一種最小加工時間的加工順序。【樣例輸入】：535871062149【樣例輸出】：34【算法分析】：本題求一個加工順序使得加工總時間最短,要使時間最短,則就是讓機器的空閑時間最短。一旦A機器開始加工,則A機器將會不停的進行作業，關鍵是B機器在加工過程中,有可能要等待A機器。很明顯第一個部件在A機器上加工時，B機器必須等待,最后一個部件在B機器上加工,A機器也在等待B機器的完工。可以大膽猜想,要使總的空閑的最少,就要把在A機器上加工時間最短的部件最先加工,這樣使得B機器能以最快的速度開始加工;把在B機器上加工時間最短的部件放在最后加工。這樣使得A機器能盡快的等待B機器完工。于是我們可以設計出這樣的貪心法：設Mi=min{ai,bi}將M按照從小到大的順序排序。然后從第1個開始處理，若Mi=ai，則將它排在從頭開始的已經作業后面，若Mi=bi，則將它排在從尾開始的作業前面。例如：N=5（a1，a2，a3，a4，a5）=（3，5，8，7，10）（b1，b2，b3，b4，b5）=（6，2，1，4，9）則（m1，m2，m3，m4，m5）=（3，2，1，4，9）排序之后為（m3，m2，m1，m4，m5）處理m3：∵m3=b3∴m3排在后面；加入m3之后的加工順序為(，，，，3)；處理m2：∵m2=b2∴m2排在后面；加入m2之后的加工順序為(，，，2，3)；處理m1：∵m3=a1∴m1排在前面；加入m1之后的加工順序為(1，，，2，3)；處理m4：∵m4=b4∴m4排在后面；加入m4之后的加工順序為(1，，4，2，3)；處理m5：∵m5=b5∴m5排在后面；加入m5之后的加工順序為(1，5，4，2，3)；則最優加工順序就是（1，5，4，2，3），最短時間為34。顯然這是最優解。問題是這種貪心策略是否正確呢？還需證明。算法流程如下：forI:=1toNdo {求M數組}ifA[I]<B[I]thenM[I]:=A[I] elseM[I]:=B[I]；將M從小到大排序；S:=1;T:=N; {首位指針初始化}forI:=1toNdoif對于第I小的工序J，若A[J]<B[J]thenbeginOrder[S]:=J;{將工序J插在加工序列的前面}S:=S+1;endelsebeginOrder[T]:=J;{將工序J插在加工序列的后面}T:=T-1;end;五、任務時間表問題?有n個任務,每個任務都需要1個時間單位執行.任務i的截止時di(1<=di<=n)表示要求任務i在時間di前結束.誤時懲罰wi表示若任務i未在時間di之前結束將導致wi的懲罰;?確定所有任務的執行順序,使得最懲罰最小;分析：?稱在限期內完成的任務為早任務,收到罰款的任務為遲任務.如果早任務緊跟在遲任務之后,交換之后總罰款不變；?假設對于相鄰兩個早任務i和i+1.由于兩個任務都是早任務,因此tj+1<=dj+1.若di>di+1,則ti+1<=di+1<di,交換以后顯然i+1的時間更早,仍然是早任務;i的時間ti’=ti+1<di仍然是早任務,總罰款不變；?規范形式:所有早任務在遲任務前,且按限期非遞減排序.?關鍵:選哪些作為早任務??不是任選一些任務作為早任務都是可行的.對于一個早任務集合S,如何判斷它是否可行呢?只需要對S內的元素按限期非遞減排序,然后一一放置；?貪心算法：先把罰款E中元素按照權值從大到小排序為e1,e2,…按照e1,e2,…的順序，嘗試添加到當前集合S里；–如果添加之后S仍是獨立集，則添加成功–如果S不是獨立集，則由定義知以后無論怎樣繼續添加元素，得到的集合都不可能重新成為獨立集，因此不能進行此添加操作；Description:一個單位時間任務是個作業,如要在計算機上運行一個程序,它恰覆蓋一個單位的運行時間。給定一個單位時間任務的集合S,對S的一個調度即S的一個排列,其中規定了這些任務的執行順序。該調度中的第一個任務開始于時間0,結束于時1;第二個任務開始于時間1,結束于時間2;……。單處理器上具有期限和罰款的單位時間任務調度問題的輸入如下:1.包含n個單位時間任務的集合S={1,2,……,n};2.n個取整的期限d1,……,dn,(1≤d,≤n),任務i要求在di前完成;3.n個非負的權(或罰款)w1,……,wn。如果任務i沒在時間di之前結束,則導致罰款wi;要求找出S的一個調度,使之最小化總的罰款。Input:第一行為一個n(n<=100)，表示n個任務，以后n行，每行兩個數di和wi分別表示期限和罰款Output:最小化總的罰款罰款問題SampleInput6610470340260450130420SampleOutput:50【算法分析】：要使罰款最少,我們顯然應盡量完成w[i]值較大的工作,此時,我們可以將工作按w[i]從大到小進行排序,然后按排好的順序依次對工作進行安排,安排的規則為:要使處理工作i的時間既在d[i]之內,又盡量靠后;如果d[i]之內的時間都已經排滿,就放棄此項工作。例如:任務i1234567期限di4243146罰款wi70605040302010最初,我們設所有n個時間空位都是空的。然后按罰款的單調遞減順序(任務1,任務2,任務3,任務4,任務5,任務6,任務7)對各個子任務作貪心選擇。在考慮任務j時,如果有一個恰處于或前于dj的時間空位仍空著,則將任務j賦與最近的這樣的空位,并填入;如果不存在這樣的空位,則將任務j賦與一個還未被占的、最近的空位。按上述貪心策略選擇了任務1,2,3,4,7,放棄任務5,6。最終的最優調度為〈2,4,3,1,7,5,6〉,其總的罰款為W5+W6＝50。六、最優合并問題?有n個正整數,每次可以合并兩個相鄰的數，得到他們的和,代價為相加后的新數.?按如何的順序把所有的數合并成一個,使得代價總和盡量小??貪心法:每次采取代價最少的合并方案?不一定得到最優解!最優解為74Description：在一個果園里,多多已經將所有的果子打了下來,而且按果子的不同種類分成了不同的堆。多多決定把所有的果子合成一堆。

每一次合并,多多可以把兩堆果子合并到一起,消耗的體力等于兩堆果子的重量之和。可以看出,所有的果子經過n-1次合并之后,就只剩下一堆了。多多在合并果子時總共消耗的體力等于每次合并所耗體力之和。

因為還要花大力氣把這些果子搬回家,所以多多在合并果子時要盡可能地節省體力。假定每個果子重量都為1,并且已知果子的種類數和每種果子的數目,你的任務是設計出合并的次序方案,使多多耗費的體力最少,并輸出這個最小的體力耗費值。

例如有3種果子,數目依次為1,2,9。可以先將1、2堆合并,新堆數目為3,耗費體力為3。接著,將新堆與原先的第三堆合并,又得到新的堆,數目為12,耗費體力為12。所以多多總共耗費體力=3+12=15。可以證明15為最小的體力耗費