1、C+程序設計程序設計貪婪算法貪婪算法崔崔 斌斌2 53什么是貪婪法什么是貪婪法n找硬幣的例子找硬幣的例子n假設有四種硬幣，面值分別為二角五分、一角假設有四種硬幣，面值分別為二角五分、一角、五分和一分。如今要找給顧客六角三分錢。、五分和一分。如今要找給顧客六角三分錢。n如何使找給顧客的硬幣數最少？如何使找給顧客的硬幣數最少？n方案：方案：2個二角五分，個二角五分，1個一角和個一角和3個一分。個一分。n背后的想法：每次都首先選擇面值最大的硬幣背后的想法：每次都首先選擇面值最大的硬幣，假設剩余錢不夠再選擇面值次大的硬幣，假設剩余錢不夠再選擇面值次大的硬幣n-貪婪法的思想貪婪法的思想3 53背包問題：

2、背包問題：給定給定n種物品和一個背包，設種物品和一個背包，設Wi為物體為物體i的分量，的分量，Vi為期價值，為期價值，C為背包的承分量。要求在背包為背包的承分量。要求在背包的承分量的限制下，進能夠使背包中物品的的承分量的限制下，進能夠使背包中物品的價值最大。價值最大。貪婪戰略一：每次選擇價值最大的物品。貪婪戰略一：每次選擇價值最大的物品。貪婪戰略二：每次選擇分量最小的物品。貪婪戰略二：每次選擇分量最小的物品。貪婪戰略三：每次選擇貪婪戰略三：每次選擇Vi/Wi最大的物品最大的物品4 53n什么是貪婪法？什么是貪婪法？n“鼠目寸光的方法？每次選擇面值最大的硬幣鼠目寸光的方法？每次選擇面值最大的硬幣

3、還是能得到正確結果的還是能得到正確結果的n貪婪法在求解問題時，每一步選擇的都是當前看貪婪法在求解問題時，每一步選擇的都是當前看來最好的選擇來最好的選擇;貪婪法的關鍵是決議每一步該怎貪婪法的關鍵是決議每一步該怎樣做。每次都試圖選擇面值最大的硬幣樣做。每次都試圖選擇面值最大的硬幣n經過一系列小的步驟構成一個解，在每一步根據經過一系列小的步驟構成一個解，在每一步根據部分情況作出最優戰略，構成問題的最優解把每部分情況作出最優戰略，構成問題的最優解把每一步選擇的最大面值的硬幣交給客戶就是硬幣總一步選擇的最大面值的硬幣交給客戶就是硬幣總個數最少的方案個數最少的方案5 53一：事件序列問題一：事件序列問題問

4、題的描畫問題的描畫知知N = 12個事件的開場時辰和終了時辰，一些個事件的開場時辰和終了時辰，一些在時間上沒有重疊的事件可以構成一個事件在時間上沒有重疊的事件可以構成一個事件序列，事件序列包含的事件數目稱為事件序序列，事件序列包含的事件數目稱為事件序列的長度。列的長度。要求找出一個最長的事件序列。要求找出一個最長的事件序列。6 53貪婪戰略一：每一步選擇最早開場事件？貪婪戰略一：每一步選擇最早開場事件？7 53貪婪戰略二：每一步選擇最短事件？貪婪戰略二：每一步選擇最短事件？8 539 53把一切的事件按終了時間由小到大排序，每一把一切的事件按終了時間由小到大排序，每一步選擇終了時間最早的事件，

5、并且和所選事步選擇終了時間最早的事件，并且和所選事件不重疊件不重疊不重疊不重疊: a事件的終了時辰小于等于事件的終了時辰小于等于b 事件的開事件的開場時辰場時辰enda = beginb 這時這時a事件和事件和b事件不重疊，即為事件不重疊，即為a = 上一個事件終了的時間上一個事件終了的時間上一個事件終了的時間上一個事件終了的時間 = endi-1begini start_time; selecti = 1; start_time = endi；11 53#include #include using namespace std;using namespace std;const int N

6、= 12;const int N = 12;void OutputResult(int select, int N) /void OutputResult(int select, int N) /輸出結果函數輸出結果函數 for(int i = 0; i N; i+) for(int i = 0; i N; i+) if(selecti = 1) / if(selecti = 1) /當標志為當標志為1 1時該事件被選中時該事件被選中 cout i endl; cout i endl; 12 53int main()int main() int beginN = 1, 3, 0, 3, 2,

7、5, 6, 4, 10, 8, 15, 15; / int beginN = 1, 3, 0, 3, 2, 5, 6, 4, 10, 8, 15, 15; /開場時間開場時間 int endN = 3, 4, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20; / int endN = 3, 4, 7, 8, 9, 10, 12, 14, 15, 18, 19, 20; /終了時間終了時間 int selectN = 0; / int selectN = 0; /標志選取哪些事件標志選取哪些事件 int i = 0; / int i = 0; /當前最早終了的事件當前最早

8、終了的事件 int time_start = 0; / int time_start = 0; /當前情況下可選事件的最早開場事件當前情況下可選事件的最早開場事件 while(i N) / while(i = time_start) / if(begini = time_start) /時間不重疊時間不重疊 selecti = 1; / selecti = 1; /選擇事件選擇事件i i time_start = endi; / time_start = endi; /更新后面事件的最早開場時間更新后面事件的最早開場時間 i+; i+; OutputResult(select, N); / O

9、utputResult(select, N); /輸出被選擇事件輸出被選擇事件 return 0; return 0; 13 53小結小結 1貪婪法的解題步驟貪婪法的解題步驟從問題的某個初始條件出發從問題的某個初始條件出發事件序列初始為空，第一步選擇第一個事件；事件序列初始為空，第一步選擇第一個事件；采用循環語句，當可以向求解目的前進一步時，采用循環語句，當可以向求解目的前進一步時，就根據部分最優戰略，得到一個部分解，減少就根據部分最優戰略，得到一個部分解，減少問題的范圍或規模問題的范圍或規模選擇最早終了的事件；選擇最早終了的事件；將一切的部分解綜合起來，得到問題的最終解將一切的部分解綜合起來

10、，得到問題的最終解每一步的最早終了事件構成最終的事件序列；每一步的最早終了事件構成最終的事件序列；14 53二：區間覆蓋問題二：區間覆蓋問題問題的描畫問題的描畫用整數用整數i來表示來表示x軸上坐標為軸上坐標為i - 1, i的區間的區間(長度長度為為1)。給出。給出M(1 = M = 200)個不同的整數，個不同的整數，表示表示M個這樣的區間。個這樣的區間。要求畫出幾條線段覆蓋住一切的區間，條件是：要求畫出幾條線段覆蓋住一切的區間，條件是：每條線段可以恣意長，但是要求所畫線段的每條線段可以恣意長，但是要求所畫線段的長度之和最小，并且線段的數目不超越長度之和最小，并且線段的數目不超越N(1= N

11、 = 50)。例如：給出例如：給出3個整數個整數2， 4， 6，就表示，就表示1, 2,3, 4, 5, 6這三個區間。這三個區間。15 53例如：給出例如：給出M = 5個整數個整數1，3，4，8，11表示表示區間，要求所用線段不超越區間，要求所用線段不超越N = 3條，可以有多種條，可以有多種覆蓋方案。覆蓋方案。8 88 87 711116 616 53貪婪戰略：每次斷開最長間隔貪婪戰略：每次斷開最長間隔17 53程序流程圖程序流程圖18 53數據構造：數據構造：positionm - 1，表示有，表示有m個線段個線段 poisitonk = i，表示線段，表示線段i - 1, i 表示每

12、兩個線段間隔的數組表示每兩個線段間隔的數組distancem-1 distancei = positioni + 1 - positioni - 1; 先求舉間隔，再排序先求舉間隔，再排序19 53假設曾經對區間間隔排序了，那么：假設曾經對區間間隔排序了，那么：distance0最大，最大，distance1其次。其次。開場總長度：開場總長度：nTotalLength =positionM-1 - position0 + 1每斷開一次，總長度減少每斷開一次，總長度減少distanceinTotalLength = nTotalLength - distancei i+, 下一次要斷開的序號。下

13、一次要斷開的序號。 循環多少次？循環多少次？ while(nLine 0)20 53int main()int main() const int M = 5; const int M = 5; const int N = 3; const int N = 3; int position = 1, 3, 4, 8, 11; / int position = 1, 3, 4, 8, 11; /表示線段表示線段0,1, 2, 3, 3,40,1, 2, 3, 3,4 int distanceM-1; / int distanceM-1; /線段之間的間隔線段之間的間隔 for(int i = 0;

14、i M - 1; i+) / for(int i = 0; i = M) /N if(N = M) /N大于等于大于等于MM的情況的情況 cout The total length is cout The total length is： M endl; M endl; return 0; return 0; 21 53 /N /N小于小于MM的情況的情況 int nLine = 1; / int nLine = 1; /當前運用的線段數當前運用的線段數 int nTotalLength = positionM-1 - position0 + 1;/ int nTotalLength = po

15、sitionM-1 - position0 + 1;/運用的線段長度運用的線段長度 int nDivide = 0; / int nDivide = 0; /指向當前未斷開的最大間隔的間隔指向當前未斷開的最大間隔的間隔 while(nLine 0) while(nLine 0) nLine+; / nLine+; /多運用一條線段多運用一條線段 nTotalLength -= distancenDivide; / nTotalLength -= distancenDivide; /斷開當前最大的間隔斷開當前最大的間隔 nDivide+; / nDivide+; /指向下一個最大間隔指向下一個最

16、大間隔 cout The total length is: nTotalLength endl; cout The total length is: nTotalLength endl; return 0; return 0; 22 53/ /從大到小排序從大到小排序void Sort(int value , int number)void Sort(int value , int number) for(int i = 0; i number; i+) for(int i = 0; i number; i+) for(int j = 0; j number - 1 - i; j+) for(

17、int j = 0; j number - 1 - i; j+) if(valuej valuej + 1) if(valuej = end1的活動的活動的一個最優的一個最優解。解。n一個最優解是一個最優解是0#，1#， 5#， 8#， 10# n1#， 5#， 8#， 10# 是一個最優解是一個最優解25 53最優子構造最優子構造用用n-1根線段的覆蓋問題是用根線段的覆蓋問題是用n根線段的覆蓋問根線段的覆蓋問題的一個子問題。并且題的一個子問題。并且n-1根線段覆蓋的最優根線段覆蓋的最優解斷開下一個最大間隔后就是用解斷開下一個最大間隔后就是用n根線段覆蓋根線段覆蓋的一個最優解。的一個最優解。當

18、遇到的問題有最優子構造的性質時，可以思當遇到的問題有最優子構造的性質時，可以思索運用貪婪法解題。索運用貪婪法解題。26 53三：最小生成樹問題三：最小生成樹問題電路系統電路系統思索有很多個電子組件的電路系統，為了使得思索有很多個電子組件的電路系統，為了使得組件組件i和組件和組件j的電勢一樣，需求把的電勢一樣，需求把i和和j用導線用導線相連。如何相互銜接組件，使他們之間的電相連。如何相互銜接組件，使他們之間的電勢都相等，并且用最短的導線長度勢都相等，并且用最短的導線長度?27 53通訊系統通訊系統思索通訊公司，如中國挪動、電信，需求構建思索通訊公司，如中國挪動、電信，需求構建一通訊網絡，銜接一通

19、訊網絡，銜接n個不同的用戶，把用戶個不同的用戶，把用戶i和用戶和用戶j連在一同的代價是連在一同的代價是ci,j。使一切用戶。使一切用戶相互銜接的最小費用是多少？相互銜接的最小費用是多少？28 53根本概念根本概念圖：包含頂點和銜接頂點的邊，假設邊沒有方向稱圖：包含頂點和銜接頂點的邊，假設邊沒有方向稱為無向圖，假設邊有方向稱為有向圖。邊帶有值為無向圖，假設邊有方向稱為有向圖。邊帶有值的圖稱為帶權圖。的圖稱為帶權圖。樹：連通無回路樹：連通無回路(沒有圈沒有圈)的無向圖，的無向圖，性質：性質：|E| = |V| - 1，E是邊的集合，是邊的集合，V是頂點集合是頂點集合29 53圖的表示方法圖的表示方

20、法30 53n問題的描畫問題的描畫n設設G = (V, E)是一個無向連通帶權圖，邊的大是一個無向連通帶權圖，邊的大小可以了解為邊的長度。假設小可以了解為邊的長度。假設G是一棵包含是一棵包含G的一切頂點的樹，且樹的邊也是的一切頂點的樹，且樹的邊也是G中的邊，中的邊，那么稱那么稱G為為G的生成樹，生成樹各邊長度的的生成樹，生成樹各邊長度的和稱為該生成樹的耗費。在和稱為該生成樹的耗費。在G的生成樹中，的生成樹中，耗費最小的生成樹稱為耗費最小的生成樹稱為G的最小生成樹。的最小生成樹。n設計算法求圖的最小生成樹。設計算法求圖的最小生成樹。31 53生成樹例如生成樹例如用什么方法使生成樹的邊的長度之和最

21、小呢，用什么方法使生成樹的邊的長度之和最小呢，即求最小生成樹？即求最小生成樹？32 53戰略之一：戰略之一：Prim算法算法初始形狀：恣意選擇一個頂點，放入集合初始形狀：恣意選擇一個頂點，放入集合S中；中；步驟：從圖的頂點集合步驟：從圖的頂點集合V - S中選擇一個頂點中選擇一個頂點j，頂點頂點j到集合到集合S中某個頂點中某個頂點i的邊的邊(i, j)的長度是的長度是一切邊中最小的，把該頂點參與集合一切邊中最小的，把該頂點參與集合S中；中； 終了形狀：終了形狀：S = V。33 53Prim算法流程圖算法流程圖34 53int c66 = 0, 4, INT_MAX, 5, INT_MAX,

22、INT_MAX, 4, 0, 1, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 1, 0, 2, 6, INT_MAX, 5, INT_MAX, 2, 0, INT_MAX, 7, INT_MAX, INT_MAX, 6, INT_MAX, 0, 3, INT_MAX, INT_MAX, INT_MAX, 7, 3, 0;35 53nS 0 lowest costnS 0，1 lowest costnS 0，1，2 lowest costnS 0，1，2，3 lowest costnS 0，1，2，3，4 lowest costnS 0，1，2，3，4，50 4 5

23、 0 4 5 0 0 0 0 0 30 0 0 0 0 30 0 1 5 0 0 1 5 0 0 0 0 6 7 0 0 0 0 6 7 0 0 0 2 6 0 0 0 2 6 選擇節點選擇節點1 136 53Prim算法實現算法實現int sN表示集合表示集合S，1表示曾經參與，否那么表示曾經參與，否那么0，初始初始S0 = 1;lowcostN記錄每一個頂點到集合記錄每一個頂點到集合s的最短邊長的最短邊長度度,初始初始lowcost0, ., N-1 = c00, ., N-1lowcostN =0,4,INT_MAX, 5, INT_MAX, INT_MAX,37 53把一個節點從把一個

24、節點從V V中放到中放到S S中中int min = INT_MAX; /int min = INT_MAX; /可以表示的最大整數范圍可以表示的最大整數范圍int j; /int j; /用來記錄下一個參與用來記錄下一個參與s s的頂點的頂點for(int k = 1; k N; k+) /for(int k = 1; k N; k+) /查找最短的邊查找最短的邊 if (lowcostk min & (!sk) if (lowcostk min & (!sk) min = lowcostk; min = lowcostk; j = k; j = k; /j /j就是要參與的

25、頂點的編號就是要參與的頂點的編號38 53closestN記錄每一個頂點到集合記錄每一個頂點到集合s的最短邊在集合的最短邊在集合s中的頂點，初始值：中的頂點，初始值：closesti = 0假設邊假設邊(j, i)是是j到集合到集合s的最短的一條邊，那么集合的最短的一條邊，那么集合S中的點是中的點是i， 既既closestj = i，邊的長度用，邊的長度用lowcostj表示表示假設參與假設參與1，closest1 = 0;由于由于1到到0的邊最短。同的邊最短。同理：理：closest2 = 1; closest3=2；closest4 = 2; closest5=4S 0 , S 0, 1

26、, S 0, 1, 2 .S 0 , S 0, 1 , S 0, 1, 2 .39 53/ /修正集合外的頂點到集合修正集合外的頂點到集合S S里的頂點最短邊的長度里的頂點最短邊的長度，即更新，即更新lowcostlowcost。由于每參與一點，其他點到集合。由于每參與一點，其他點到集合里面點的邊長都會發生變化。里面點的邊長都會發生變化。j j是新參與的節點是新參與的節點for(int k = 1; k N; k+)for(int k = 1; k N; k+) if(cjk lowcostk) & (!sk) if(cjk lowcostk) & (!sk) lowcostk

27、 = cjk; lowcostk = cjk; closestk = j; /closest closestk = j; /closest代表一個頂點代表一個頂點 40 53#include #include #include #include using namespace std;using namespace std;const int N = 6;const int N = 6;int c66 = /int c66 = /存儲圖存儲圖 0, 4, INT_MAX, 5, INT_MAX, INT_MAX, 0, 4, INT_MAX, 5, INT_MAX, INT_MAX, 4, 0

28、, 1, INT_MAX, INT_MAX, INT_MAX, 4, 0, 1, INT_MAX, INT_MAX, INT_MAX, INT_MAX, 1, 0, 2, 6, INT_MAX, INT_MAX, 1, 0, 2, 6, INT_MAX, 5, INT_MAX, 2, 0, INT_MAX, 7, 5, INT_MAX, 2, 0, INT_MAX, 7, INT_MAX, INT_MAX, 6, INT_MAX, 0, 3, INT_MAX, INT_MAX, 6, INT_MAX, 0, 3, INT_MAX, INT_MAX, INT_MAX, 7, 3, 0, INT_

29、MAX, INT_MAX, INT_MAX, 7, 3, 0,; ;int main()int main() Prim(); Prim(); return 0; return 0; 41 53void Prim()void Prim() int lowcostN; / int lowcostN; /記錄每一個頂點到集合記錄每一個頂點到集合s s的最短邊長度的最短邊長度 int closestN; / int closestN; /記錄每一個頂點到集合記錄每一個頂點到集合s s的最短邊的最短邊 / /在集合在集合s s中的頂點中的頂點 int sN; / int sN; /集合集合s s，記錄曾

30、經參與的頂點，記錄曾經參與的頂點，1 1表示該表示該 / /頂點曾經參與頂點曾經參與s s s0 = 1; / s0 = 1; /初始化，首先參與號頂點初始化，首先參與號頂點 for(int i = 1; i N; i+) / for(int i = 1; i N; i+) /更新其它頂點到集合更新其它頂點到集合s s的間隔的間隔 lowcosti = c0i; /i lowcosti = c0i; /i到到s s的最短邊的長度的最短邊的長度 closesti = 0; /i closesti = 0; /i到到s s的最短邊的另外一個頂點的最短邊的另外一個頂點 si = 0; si = 0;

31、 42 53 / /還需求參與還需求參與N - 1N - 1個頂點，每一步都是貪婪選擇個頂點，每一步都是貪婪選擇 i = 1; i = 1; while(i N) while(i N) int min = INT_MAX; int min = INT_MAX; int j int j，k; /k; /用來記錄下一個參與用來記錄下一個參與s s的頂點的頂點 for(k = 1; k N; k+) / for(k = 1; k N; k+) /查找最短的邊查找最短的邊 if(lowcostk min & (!sk) if(lowcostk min & (!sk) min = low

32、costk; j = k; min = lowcostk; j = k; cout Node j :( j ,“ closestj ) = lowcostj endl; cout Node j :( j ,“ closestj ) = lowcostj endl; sj = 1; / sj = 1; /把把j j參與到參與到s s中中 for(k = 1; k N; k+) / for(k = 1; k N; k+) /修正剩余頂點到集合修正剩余頂點到集合s s的頂點最短邊的長度的頂點最短邊的長度 if(cjk lowcostk) & (!sk) if(cjk lowcostk) &a

33、mp; (!sk) lowcostk = cjk; closestk = j; lowcostk = cjk; closestk = j; i+; i+; 43 53戰略之二：戰略之二：Kruskal算法算法初始形狀：一切頂點孤立，沒有邊；初始形狀：一切頂點孤立，沒有邊； 步驟：按邊的長度由小到大陳列，不斷插入一條步驟：按邊的長度由小到大陳列，不斷插入一條邊，只需不構成回路，就把邊插入；假設構成邊，只需不構成回路，就把邊插入；假設構成回路，那么放棄這條邊，選擇下一個最小邊；回路，那么放棄這條邊，選擇下一個最小邊；終了形狀：插入邊的數目到達了終了形狀：插入邊的數目到達了|V| - 1。44 53

34、Kruskal算法流程圖算法流程圖45 53貪婪的性質貪婪的性質每個階段面臨的問題都是原問題的一個子問題每個階段面臨的問題都是原問題的一個子問題子問題的處理只與當前階段和以后階段的決策子問題的處理只與當前階段和以后階段的決策有關有關與以前各階段的決策無關與以前各階段的決策無關46 53貪婪算法的缺乏貪婪算法的缺乏貪婪法的留意點貪婪法的留意點-貪婪法不是萬能的貪婪法不是萬能的假設找硬幣的例子：硬幣的面值有：一分、五假設找硬幣的例子：硬幣的面值有：一分、五分、八分、一角，假設要找給客戶的錢是一分、八分、一角，假設要找給客戶的錢是一角三分。角三分。運用貪婪法的方案是：運用貪婪法的方案是：1個一角和個

35、一角和3個一分個一分而最優的方案是：而最優的方案是：1個八分和個八分和1個個5分分所以運用貪婪法時需求留意最終得到的是不是所以運用貪婪法時需求留意最終得到的是不是問題的最優解問題的最優解47 53啟發式算法和次優解啟發式算法和次優解貪婪法是一種不追求最優解，只希望得到較為稱心解的方法。貪婪法是一種不追求最優解，只希望得到較為稱心解的方法。例如找硬幣問題，不思索找零錢的一切各種發表方案，而是從例如找硬幣問題，不思索找零錢的一切各種發表方案，而是從最大面值的幣種開場，按遞減的順序思索各幣種，先盡量用最大面值的幣種開場，按遞減的順序思索各幣種，先盡量用大面值的幣種，當缺乏大面值幣種的金額時才去思索下

36、一種大面值的幣種，當缺乏大面值幣種的金額時才去思索下一種較小面值的幣種。較小面值的幣種。這種方法并不是總是最優。如只需面值分別為這種方法并不是總是最優。如只需面值分別為1、5和和11單位的單位的硬幣，而希望找回總額為硬幣，而希望找回總額為15單位的硬幣。按貪新算法，應找單位的硬幣。按貪新算法，應找1個個11單位面值的硬幣和單位面值的硬幣和4個個1單位面值的硬幣，共找回單位面值的硬幣，共找回5個硬個硬幣。但最優的解應是幣。但最優的解應是3個個5單位面值的硬幣單位面值的硬幣貪婪法普通可以快速得到稱心的解，由于它省去了為找最優解貪婪法普通可以快速得到稱心的解，由于它省去了為找最優解要窮盡一切能夠而必

37、需耗費的大量時間。要窮盡一切能夠而必需耗費的大量時間。貪婪法常以當前情況為根底作最優選擇，而不思索各種能夠的貪婪法常以當前情況為根底作最優選擇，而不思索各種能夠的整體情況，所以不要回溯。整體情況，所以不要回溯。48 53n問題描畫問題描畫n設有編號為設有編號為0、1、n-1的的n種物品，體積分別為種物品，體積分別為v0、v1、vn-1。將這。將這n種物品裝到容量都為種物品裝到容量都為V的假設干箱子里。商的假設干箱子里。商定這定這n種物品的體積均不超越種物品的體積均不超越V，即對于，即對于0in，有，有0viV。不同的裝箱方案所需求的箱子數目能夠不同。裝箱問題要。不同的裝箱方案所需求的箱子數目能

38、夠不同。裝箱問題要求使裝盡這求使裝盡這n種物品的箱子數要少。種物品的箱子數要少。n假設調查將假設調查將n種物品的集合分劃成種物品的集合分劃成n個或小于個或小于n個物品的一切個物品的一切子集，最優解就可以找到。但一切能夠劃分的總數太大。對子集，最優解就可以找到。但一切能夠劃分的總數太大。對適當大的適當大的n，找出一切能夠的劃分要破費的時間是無法接受的，找出一切能夠的劃分要破費的時間是無法接受的。為此，對裝箱問題采用非常簡單的近似算法，即貪婪法。為此，對裝箱問題采用非常簡單的近似算法，即貪婪法。裝箱問題裝箱問題49 53n不失普通性，設不失普通性，設n件物品的體積是按從大到小排好序的，即有件物品的

39、體積是按從大到小排好序的，即有v0v1vn-1。如不滿足上述要求，只需先對這。如不滿足上述要求，只需先對這n件物品按它件物品按它們的體積從大到小排序，然后按排序結果對物品重新編號即可們的體積從大到小排序，然后按排序結果對物品重新編號即可。裝箱算法簡單描畫如下：。裝箱算法簡單描畫如下：n輸入箱子的容積輸入箱子的容積V；輸入物種類數；輸入物種類數n；輸入各物品的體積，排序；輸入各物品的體積，排序預置已用箱子鏈為空；預置已用箱子鏈為空； 預置已用箱子計數器預置已用箱子計數器box_count為為0；for (i = 0; i n; i+)for (i = 0; i n; i+) 從第一只箱子開場順序尋覓能放入