高中信息競賽貪心算法

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

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

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

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

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

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

第3-n+2行每行包含一個正整數(shù)Pi(5<=Pi<=w)w表示所對應(yīng)紀(jì)念品的價格。Output：輸出文件group.out僅一行，包含一個整數(shù)，為最少的分組數(shù)目和。應(yīng)用舉例3---紀(jì)念品分組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;應(yīng)用舉例4---排隊打水問題【問題描述】：有N個人排隊到R個水龍頭去打水,他們裝滿水桶的時間為T1,T2,…,Tn為整數(shù)且各不相等,應(yīng)如何安排他們的打水順序才能使他們花費的時間最少？【分析】：由于排隊時,越靠前面的計算的次數(shù)越多,顯然越小的排在越前面得出的結(jié)果越小(可以用數(shù)學(xué)方法簡單證明),所以這道題可以用貪心法解答,基本步驟：1.將輸入的時間按從小到大排序；2.將排序后的時間按順序依次放入每個水龍頭的隊列中；3.統(tǒng)計，輸出答案。應(yīng)用舉例5---取數(shù)游戲2341

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

運用貪心策略解題時，有的題目有不止一種可能的貪心標(biāo)準(zhǔn)，但不一定每種貪心標(biāo)準(zhǔn)都能夠得到正確的結(jié)果。因此，在運用貪心法時，一定要仔細分析，選擇恰當(dāng)?shù)呢澬臉?biāo)準(zhǔn)。應(yīng)用舉例6---混合牛奶1648

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

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

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

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

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

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

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

應(yīng)用舉例7---數(shù)列極差問題1647

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

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

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

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

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

例如N=4，4堆紙牌數(shù)分別為：

①9②8③17④6

移動3次可達到目的：

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

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

4

98176

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

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

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

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

Description：一個整數(shù)區(qū)間[A,B],A

請編程完成以下任務(wù)：

1.從文件中讀取區(qū)間的個數(shù)及其它們的描述；

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

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

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

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

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

例如有3種果子,數(shù)目依次為1,2,9?？梢韵葘?、2堆合并,新堆數(shù)目為3,耗費體力為3。接著,將新堆與原先的第三堆合并,又得到新的堆,數(shù)目為12,耗費體力為12。所以多多總共耗費體力=3+12=15?？梢宰C明15為最小的體力耗費