【正文】 1 圖 （ a）旅行費(fèi)用拓?fù)? 二、解題策略 按照貪心策略，在局部尋優(yōu)的過程可以用 圖 （ b） 表示，得到的路徑為 ABECDA，總費(fèi)用為 10+30+20+12+80=152。顯然，這一結(jié)果并非最優(yōu)。因?yàn)?，最?yōu)路徑為 ABEDCA，總費(fèi)用為 10+30+30+12+21=103。 A E D C B 50 30 80 30 20 12 43 10 36 21 B A E D C 50 12 80 30 20 10 80 21 30 D C 43 E 36 C D D A 第 1步 ， 選擇 B 第 2步，選擇 E 第 3步，選擇 C 第 4步，選擇 D （ a）旅行費(fèi)用拓?fù)? （ b）貪心法求解問題 圖 旅行費(fèi)用問題 程序框架 1. 數(shù)據(jù)結(jié)構(gòu) （ 1）費(fèi)用網(wǎng)絡(luò)描述 (用圖的鄰接矩陣的描述 )： int expense[4][] ={{ 0, 10, 21, 80, 50}, { 10, 0, 36, 43, 30}, { 21, 36, 0, 12, 20}, { 80, 43, 12, 0, 30} { 50, 30, 20, 30, 0}}。 （ 2）定義枚舉變量 enum scenes{a,b,c,d,e}。 這樣，就會(huì)形成如下對應(yīng)關(guān)系： expense[a][b] ~ expense[0][1] ~ 10 expense[a][c] ~ expense[0][2] ~ 21 expense[a][d] ~ expense[0][3] ~ 80 expense[b][c] ~ expense[0][4] ~ 50 expense[b][c] ~ expense[1][2] ~ 36 expense[b][d] ~ expense[1][3] ~ 43 expense[a][e] ~ expense[1][4] ~ 30 …… 2. 貪心過程 { 初始化所有節(jié)點(diǎn)的費(fèi)用標(biāo)志； 設(shè)置出發(fā)節(jié)點(diǎn) V； for( i =1。 i= n1。 i + +) { s = 從 V至所有未曾到過的景點(diǎn)中費(fèi)用最少的景點(diǎn)； 累加費(fèi)用； V = s； /* 新的起點(diǎn) */ 設(shè)置 V的已訪問標(biāo)志； } 最后一個(gè)景點(diǎn)返回第一個(gè)景點(diǎn)，累加費(fèi)用； } 三、程序的實(shí)現(xiàn) define N 5 /*節(jié)點(diǎn)個(gè)數(shù) */ main() { int expense[N][N] ={{0,10,21,80,50}, {10,0,36,43,30}, {21,36,0,12,20}, {80,43,12,0,30}, {50,30,20,30,0}}。 enum scenes{a,b,c,d,e} 。 enum scenes v,s。 enum scenes start,j。 unsigned int sum=0,min。 int flag[N]={0,0,0,0,0}。 int i。 v=a。 /*設(shè)置出發(fā)節(jié)點(diǎn) */ start=v。 三、程序的實(shí)現(xiàn)（續(xù)） for(i=1。i=N1。i++) { min=65535。 /* 設(shè)置一個(gè)盡量大的值 */ for(j=a。j=N1。j++) { if(flag[j]==0amp。amp。expense[v][j]!=0) if(expense[v][j]min) { min=expense[v][j]。 s=j。 } } sum=sum+min。 flag[v]=1。 /* v已訪問標(biāo)志 */ v=s。 /* 新的起點(diǎn) */ } sum=sum+expense[v][start]。 /* 最后一個(gè)景點(diǎn)返回第一個(gè)景點(diǎn)，累加費(fèi)用 */ printf(sum=%d\n,sum)。 } 四、程序測試 （ 1）測試 1 當(dāng) v=a時(shí)， sum=152 （ 2）測試 2 當(dāng) v=b時(shí)， sum=103 （ 3）測試 3 當(dāng) v=c時(shí)， sum=103 五、編程練習(xí) 用貪心法求解下列問題，并分析這些問題用貪心法能否得到整體最優(yōu)解。 1. 背包問題：一個(gè)強(qiáng)盜進(jìn)入一家商店要拿走一批物品。強(qiáng)盜只有一個(gè)最多只能裝 W斤的背包。他拿東西的原則是背一包最值錢的東西。該商店中有 N件物品，每件物品的重量和價(jià)值都是不一樣的：第 i件物品值 vi元，重 wi斤（ 1≤i≤N）。這就是著名的背包問題。 子問題 1：當(dāng)每一件物品都不可分割時(shí)，強(qiáng)盜只能對某件物品選擇帶走，還是不帶走。這就是 01背包問題。 子問題 2：當(dāng)每一件物品都可分割時(shí)，強(qiáng)盜只能對某件物品選擇帶走，還是不帶走。這就是部分背包問題。 要求分別考慮下列策略： （ 1）每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？ （ 2）每次挑選所占空間最輕的物品裝入，是否能得到最優(yōu)解？ （ 3）每次選取單位容量價(jià)值最大的物品，成為解本題的策略。 五、編程練習(xí)（續(xù)） 2. 找硬幣問題：有 n種硬幣，面值分別為 c c … 、 。若要找給顧客的錢為 x，如何找，拿出的硬幣個(gè)數(shù)最少？ 例如： n=4， c1=2 c2= c3= c4= x=67. 3. 古代埃及人有一個(gè)非常奇怪的習(xí)慣，他們喜歡把一個(gè)分?jǐn)?shù)表示為若干個(gè)分子為 1的分?jǐn)?shù)之和的形式，如： 7/8=1/2+1/3+1/24。因此人們常把分子為 1的分?jǐn)?shù)稱為埃及分?jǐn)?shù)。試給出把一個(gè)真分?jǐn)?shù)表示為埃及分?jǐn)?shù)之和的算法。 提示：數(shù)學(xué)家菲波那契提出的貪心算法如下： （ 1）設(shè)某個(gè)真分?jǐn)?shù)的分子為 A，分母為 B； （ 2）把 B除以 A的商的整數(shù)部分加 1后的值作為埃及分?jǐn)?shù)的某一個(gè)分母； （ 3）將 A乘以 C減去 B作為新的 A； （ 4）將 B乘以 C作為新的 B； （ 5）如果 A大于 1且能整除 B，則最后一個(gè)分母為 B/A； （ 6）如果 A＝ 1，則最后一個(gè)分母為 B； （ 7）否則轉(zhuǎn)步驟（ 2）。 刪數(shù)問題 一、問題描述 由鍵盤輸入一個(gè)長整數(shù) N（不超過 240位），去掉其中的任意 S個(gè)數(shù)字，剩下的數(shù)字按原來的左右順序組成一個(gè)新的整數(shù)。對給定 N和 S，尋找一種方案，使剩下的數(shù)字組成的新數(shù)最?。榱撕喕绦?，對輸入數(shù)據(jù)可不進(jìn)行判錯(cuò)處理）。要求輸出無空格的數(shù)字串。 二、解題策略 1. 長整數(shù)表示 本題要求輸入一個(gè)長度可達(dá) 240位的整數(shù)。但是， C語言中長整數(shù)（ long int）的十進(jìn)制最大長度是 19位（ 32位系統(tǒng)）。因此，要表示 240位的長整數(shù)，就要使用非常規(guī)方法： （ 1）用一個(gè)可含 256個(gè)字符的字符串代替長整數(shù) . （ 2）將一個(gè)長整數(shù)存儲(chǔ)在一個(gè)整型數(shù)組中。每一個(gè)數(shù)組元素中包含一個(gè) 4位十進(jìn)制數(shù)。 這里考慮 采用字符串方法 。 2. 選擇貪心策略 （ 1）從數(shù)字串中的最左端的一個(gè)遞減區(qū)間，刪去該區(qū)間的首字符。如 圖 。 2 7 6 8 5 9 2 3 2 6 8 5 9 2 3 2 6 5 9 2 3 2 5 9 2 3 2 5 2 3 2 2 3 （ 2）無遞減空間，則刪除最后一個(gè)數(shù)字。 圖 刪數(shù)問題 三、算法設(shè)計(jì) void getMinInteger(char * digitStr, /* 數(shù)字串 */ int n) /* 被刪個(gè)數(shù) */ { int i,j,flag=0。 char * strTemp。 for(j=n。j0。j) /* 逐一刪除 n個(gè)數(shù)字 */ { for(i=0。istrlen(digitStr)2。i++) /* 搜索遞減空間 */ { if(*(digitStr+i)*(digitStr+i+1))/* 存在遞減空間 */ { striDel(digitStr,i)。 /* 刪除第 i個(gè)數(shù)字 */ flag =1。 break。 } } if(flag= =0) /* 無遞減空間 */ *（ digitStr+(strlen(digitStr)1)） =’\0’。/* 刪除最后數(shù)字 */ } } 刪除第 i個(gè)數(shù)字的函數(shù) char *striDel(char *str,int i) { *(str+i)=39。\039。 return(strcat(str,str+i+1))。 } 四、說明 一般來說，適合貪心策略的問題大多數(shù)具有兩個(gè)特征： （ 1）貪心選擇性質(zhì) 貪心選擇性質(zhì)就是可以通過局部最優(yōu)選擇達(dá)到全局最優(yōu)。這種局部選擇可能依賴于已經(jīng)作出的所有選擇，但不依賴有待于做的選擇或子問題的解。例如本題中，當(dāng)前要?jiǎng)h除的數(shù)不依賴于將來要?jiǎng)h除的數(shù)，只考慮當(dāng)前最優(yōu)。 （ 2）最優(yōu)子結(jié)構(gòu) 問題的最優(yōu)解包含了子問題的最優(yōu)解，稱為最優(yōu)子結(jié)構(gòu)。例如本題中的數(shù) 27685923，要?jiǎng)h去 4個(gè)數(shù)字，肯定要?jiǎng)h去‘ 768’和‘ 9’。而采用貪心策略時(shí)，要依次刪去‘ 7’、‘ 8’、‘ 6’、‘ 9’。即問題的最優(yōu)解包含了 4個(gè)子問題的解。 五、程序及其測試 1. 程序 include include char *striDel(char *str,int i)。 void getMinInteger(char * digitStr,int n)。 void getMinInteger(char * digitStr,int n) { int i,j,flag=0。 char * strTemp。 for(j=n。j0。j) /* 逐一刪除 n個(gè)數(shù)字 */ { flag=0。 for(i=0。istrlen(digitStr)2。i++) /* 搜索遞減空間 */ { if(*(digitStr+i)*(digitStr+i+1)) /* 存在遞減空間 */ { striDel(digitStr,i)。 /* 刪除第 i個(gè)數(shù)字 */ flag =1。 break。 } } if(flag==0) /* 無遞減空間 */ *(digitStr+(strlen(digitStr)1))=39。\039。 /* 刪除最后數(shù)字 */ } } 程序（續(xù)） /*刪除第 i個(gè)數(shù)字的函數(shù) */ char *striDel(char *str,int i) { *(str+i)=39。\039。 return(strcat(str,str+i+1))。 } main( ) { char *digitStr。 int n。 printf(請輸入一個(gè)數(shù)字串： )。 scanf(%s,digitStr)。 printf(請輸入需刪除數(shù)字個(gè)數(shù)： )。 scanf(%d,amp。n)。 getMinInteger(digitStr,n)。 printf(%s,digitStr)。 } 2. 測試結(jié)果 （ 1）測試 1 請輸入一個(gè)數(shù)字串： 897654 請輸入需刪除數(shù)字個(gè)數(shù)： 3 654 （ 2）測試 2 請輸入一個(gè)數(shù)字串： 456789 請輸入需刪除數(shù)字個(gè)數(shù)： 2 4567 六、編程練習(xí) 1. 輸入一個(gè)數(shù)字串（位數(shù)小于 200），在其中添入 m（ m小于 20）個(gè)加號(hào)，使其值最小。 2. 汽車加油問題：某汽車加滿一次油后可以行駛 n公里路程。某次旅行的總路程為 s公里，并且該路程中共有 m個(gè)加油站。 要求：沿途加油次數(shù)最少。 輸入：每個(gè)加油站距出發(fā)點(diǎn)的距離。 輸出：汽車加油的加油站序列號(hào)。 六、編程練習(xí)（續(xù)） 3. 機(jī)器調(diào)度問題：現(xiàn)有 N項(xiàng)任務(wù)和無限多臺(tái)機(jī)器。任務(wù)可以在機(jī)器上處理。每件任務(wù)開始時(shí)間和完成時(shí)間如 表 。 在可行分配中每臺(tái)機(jī)器在任何時(shí)刻最多處理一個(gè)任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。請就本題給出的條件，求出最優(yōu)分配。 提示：一種獲得最優(yōu)分配的貪婪方法是逐步分配任務(wù)。每步分配一件任務(wù)，且按任務(wù)開始時(shí)間的非遞減次序進(jìn)行分配。若已經(jīng)至少有一件任務(wù)分配給某臺(tái)機(jī)器，則稱這臺(tái)機(jī)器是舊的；若機(jī)器非舊，則它是新的。在選擇機(jī)器時(shí)，采用以下貪婪準(zhǔn)則：根據(jù)欲分配任務(wù)的開始時(shí)間，若此時(shí)有舊的機(jī)器可用，則將任務(wù)分給舊的機(jī)器。否則，將任務(wù)分配給一臺(tái)新的機(jī)器。 如 圖 ，