【正文】 否則，將任務(wù)分配給一臺(tái)新的機(jī)器。若已經(jīng)至少有一件任務(wù)分配給某臺(tái)機(jī)器，則稱這臺(tái)機(jī)器是舊的；若機(jī)器非舊，則它是新的。 提示：一種獲得最優(yōu)分配的貪婪方法是逐步分配任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。每件任務(wù)開(kāi)始時(shí)間和完成時(shí)間如 表 。 六、編程練習(xí)（續(xù)） 3. 機(jī)器調(diào)度問(wèn)題：現(xiàn)有 N項(xiàng)任務(wù)和無(wú)限多臺(tái)機(jī)器。 輸入：每個(gè)加油站距出發(fā)點(diǎn)的距離。某次旅行的總路程為 s公里，并且該路程中共有 m個(gè)加油站。 } 2. 測(cè)試結(jié)果 （ 1）測(cè)試 1 請(qǐng)輸入一個(gè)數(shù)字串： 897654 請(qǐng)輸入需刪除數(shù)字個(gè)數(shù)： 3 654 （ 2）測(cè)試 2 請(qǐng)輸入一個(gè)數(shù)字串： 456789 請(qǐng)輸入需刪除數(shù)字個(gè)數(shù)： 2 4567 六、編程練習(xí) 1. 輸入一個(gè)數(shù)字串（位數(shù)小于 200），在其中添入 m（ m小于 20）個(gè)加號(hào)，使其值最小。 getMinInteger(digitStr,n)。 scanf(%d,amp。 scanf(%s,digitStr)。 int n。 return(strcat(str,str+i+1))。 /* 刪除最后數(shù)字 */ } } 程序（續(xù)） /*刪除第 i個(gè)數(shù)字的函數(shù) */ char *striDel(char *str,int i) { *(str+i)=39。 } } if(flag==0) /* 無(wú)遞減空間 */ *(digitStr+(strlen(digitStr)1))=39。 /* 刪除第 i個(gè)數(shù)字 */ flag =1。istrlen(digitStr)2。j) /* 逐一刪除 n個(gè)數(shù)字 */ { flag=0。 for(j=n。 void getMinInteger(char * digitStr,int n) { int i,j,flag=0。 五、程序及其測(cè)試 1. 程序 include include char *striDel(char *str,int i)。而采用貪心策略時(shí)，要依次刪去‘ 7’、‘ 8’、‘ 6’、‘ 9’。 （ 2）最優(yōu)子結(jié)構(gòu) 問(wèn)題的最優(yōu)解包含了子問(wèn)題的最優(yōu)解，稱為最優(yōu)子結(jié)構(gòu)。這種局部選擇可能依賴于已經(jīng)作出的所有選擇，但不依賴有待于做的選擇或子問(wèn)題的解。 return(strcat(str,str+i+1))。/* 刪除最后數(shù)字 */ } } 刪除第 i個(gè)數(shù)字的函數(shù) char *striDel(char *str,int i) { *(str+i)=39。 break。i++) /* 搜索遞減空間 */ { if(*(digitStr+i)*(digitStr+i+1))/* 存在遞減空間 */ { striDel(digitStr,i)。j) /* 逐一刪除 n個(gè)數(shù)字 */ { for(i=0。 for(j=n。 圖 刪數(shù)問(wèn)題 三、算法設(shè)計(jì) void getMinInteger(char * digitStr, /* 數(shù)字串 */ int n) /* 被刪個(gè)數(shù) */ { int i,j,flag=0。如 圖 。 這里考慮 采用字符串方法 。因此，要表示 240位的長(zhǎng)整數(shù)，就要使用非常規(guī)方法： （ 1）用一個(gè)可含 256個(gè)字符的字符串代替長(zhǎng)整數(shù) . （ 2）將一個(gè)長(zhǎng)整數(shù)存儲(chǔ)在一個(gè)整型數(shù)組中。 二、解題策略 1. 長(zhǎng)整數(shù)表示 本題要求輸入一個(gè)長(zhǎng)度可達(dá) 240位的整數(shù)。對(duì)給定 N和 S，尋找一種方案，使剩下的數(shù)字組成的新數(shù)最?。榱撕?jiǎn)化程序，對(duì)輸入數(shù)據(jù)可不進(jìn)行判錯(cuò)處理）。 提示：數(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）。因此人們常把分子為 1的分?jǐn)?shù)稱為埃及分?jǐn)?shù)。 五、編程練習(xí)（續(xù)） 2. 找硬幣問(wèn)題：有 n種硬幣，面值分別為 c c … 、 。這就是部分背包問(wèn)題。這就是 01背包問(wèn)題。這就是著名的背包問(wèn)題。他拿東西的原則是背一包最值錢的東西。 1. 背包問(wèn)題：一個(gè)強(qiáng)盜進(jìn)入一家商店要拿走一批物品。 /* 最后一個(gè)景點(diǎn)返回第一個(gè)景點(diǎn)，累加費(fèi)用 */ printf(sum=%d\n,sum)。 /* v已訪問(wèn)標(biāo)志 */ v=s。 } } sum=sum+min。expense[v][j]!=0) if(expense[v][j]min) { min=expense[v][j]。j++) { if(flag[j]==0amp。 /* 設(shè)置一個(gè)盡量大的值 */ for(j=a。i=N1。 /*設(shè)置出發(fā)節(jié)點(diǎn) */ start=v。 int i。 unsigned int sum=0,min。 enum scenes v,s。 i + +) { s = 從 V至所有未曾到過(guò)的景點(diǎn)中費(fèi)用最少的景點(diǎn)； 累加費(fèi)用； V = s； /* 新的起點(diǎn) */ 設(shè)置 V的已訪問(wèn)標(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}}。 這樣，就會(huì)形成如下對(duì)應(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. 貪心過(guò)程 { 初始化所有節(jié)點(diǎn)的費(fèi)用標(biāo)志； 設(shè)置出發(fā)節(jié)點(diǎn) V； for( i =1。 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）貪心法求解問(wèn)題 圖 旅行費(fèi)用問(wèn)題 程序框架 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}}。顯然，這一結(jié)果并非最優(yōu)。圖中標(biāo)出了五個(gè)景點(diǎn)之間的交通費(fèi)用。因此，初學(xué)者應(yīng)當(dāng)通過(guò)分析和經(jīng)驗(yàn)積累，了解哪些問(wèn)題適合用貪心策略，并掌握如何選擇合適的貪心策略。 ? 顯然，貪心策略不能保證對(duì)所有的問(wèn)題求得的最后解都是最優(yōu)的，特別是不能用來(lái)求最大或最小解問(wèn)題。 A K H B F C D E G J I 圖 一張地圖 貪心策略 ? 貪心策略（ greedy method）是一種企圖通過(guò)局部最優(yōu)達(dá)到全局最優(yōu)的策略，猶如登山，并非一開(kāi)始就選擇出一條到達(dá)山頂?shù)淖罴崖肪€，而是首先在視力能及的范圍內(nèi)，看中一個(gè)高處目標(biāo)，選擇一條最佳路徑；然后在新的起點(diǎn)上，再選擇一條往上爬的最佳路徑； …… ；企圖通過(guò)每一階段的最佳路徑，構(gòu)造全局的最佳路徑。直到 1976年，美國(guó)數(shù)學(xué)家 電子計(jì)算機(jī)才證明了這一猜想，并稱之為四色定理。那么印制地圖時(shí)，最少需要準(zhǔn)備幾種顏色就能達(dá)到相鄰區(qū)塊要用不同的顏色表示的要求呢？一百多年前，英國(guó)的格色離提出了最少色數(shù)為 4的猜想（ 4colours conjecture）。 1 2 3 4 8 7 6 5 （ a）魔板的一個(gè)初始狀態(tài) 1 2 3 4 8 7 6 5 （ b）上下行互換 1 2 3 4 8 7 6 5 （ c）兩行同時(shí)循環(huán)右移一格 1 2 3 4 8 7 6 5 （ d）中間 4塊順時(shí)針旋轉(zhuǎn)一格 圖 魔板 請(qǐng)編寫(xiě)一個(gè)程序，通過(guò)一系列基本操作，可以將魔板從原始狀態(tài)變?yōu)橐粋€(gè)輸入的目標(biāo)狀態(tài)。它有 3種基本玩法，以 圖 （ a） 為初始狀態(tài)這 3種玩法分別如 圖 （ b）、（ c）、（ d）所示。 圖 控制方格棋盤(pán)游戲 五、編程練習(xí)（續(xù)） 6. 魔板問(wèn)題： Rubik先生發(fā)明了一種玩具，稱為魔板。于是，在棋盤(pán)的 X個(gè)位置各放一個(gè)黑子，就可以控制整個(gè)棋盤(pán)。用回溯法求解本題。當(dāng)郵資從 1開(kāi)始，在增量為 1的情況下，請(qǐng)給出可能獲得的郵資值的最大連續(xù)區(qū)及獲得此區(qū)域的各種面值的集合。 4. 郵票問(wèn)題：設(shè)想一個(gè)國(guó)家發(fā)行的幾種面值不同的郵票。令 wij 是從投資者 j 那里得到的零件 i 的重量， cij 則為該零件的耗費(fèi)。例如自然數(shù) 5，可以有如下一些拆分方法： 5=1+1+1+1+1 5=1+1+1+2 5=1+2+2 5=1+1+3 5=1+4（與 5=4+1看成同一種拆分） 5=2+3 請(qǐng)?jiān)O(shè)計(jì)一個(gè)對(duì)任意自然數(shù)，找出所有拆分方法的程序。請(qǐng)為三位訓(xùn)獸師設(shè)計(jì)一個(gè)安全的渡河方案。 /*調(diào)用迷宮矩陣打印函數(shù) */ } 五、編程練習(xí) 1. 三個(gè)獵人雜技團(tuán)的三位訓(xùn)獸師帶著三只猴子過(guò)河，只有一條最多只能乘二人的船，人猴體重相當(dāng)，且猴子也會(huì)劃船。 mazeExpand(start)。 maze[Si][Sj]=1。 (*start).y=Sj。 /* 入口坐標(biāo) */ MAZE_NODE *start。 } } 四、測(cè)試程序 include include include include include int maze[][7]={{2,2,2,2,2,2,2},{2,0,0,0,0,0,2},{2,0,2,0,2,0,2}, {2,0,0,2,0,2,2},{2,2,0,2,0,2,2},{2,0,0,0,0,0,2},{2,2,2,2,2,2,2}}。j++) printf(%d,maze[i][j])。i++) { for(j=0。 for(i=0。 /* 擴(kuò)展新棧頂節(jié)點(diǎn) */ } （ 3）輸出函數(shù) /*在 */ prnt() { int i,j。 push(new1)。 (*new1).nodeState=1。 } if(maze[i][j1]==0) { (*new1).x=i。 maze[i+1][j]=1。 (*new1).y=j。 push(new1)。 (*new1).nodeState=1。 } if(maze[i][j+1]==0) { (*new1).x=i。 maze[i1][j]=1。 (*new1).y=j。 push(old)。 return。 maze[i][j]=2。amp。amp。 return。 maze[i][j]=2。amp。amp。 return。 maze[i][j]=2。amp。amp。 return。 maze[i][j]=2。amp。