算法分析與設計課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：28 大?。?23.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩27頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、　　目錄　　一、問題描述1　　1、普通背包問題1　　2、0-1背包問題1　　3、棋盤覆蓋問題1　　二、問題

2、分析2　　1、普通背包問題2　　2、0-1背包問題2　　3、棋盤覆蓋問題3　　三、算法設計3　　1、普通背包問題3

3、2、0-1背包問題4　　3、棋盤覆蓋問題4　　四、算法實現(xiàn)6　　1、普通背包問題6　　2、0-1背包問題8　　3、棋盤覆蓋問題10<

4、b>　　五、測試分析11　　1、普通背包問題11　　2、0-1背包問題13　　3、棋盤覆蓋問題15　　六、結論16　　七、源程序17&l

5、t;/b>　　1、普通背包問題17　　2、0-1背包問題20　　3、棋盤覆蓋問題24　　八、參考文獻26　　一、問題描述

6、　　1、普通背包問題　　有一個背包容量為C，輸入N個物品，每個物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求選擇放入的物品，不超過背包的容量，且得到的收益最好。物品可以拆分，利用貪心算法解決。　　2、0-1背包問題<

7、;p>　　在0/1背包問題中，需對容量為c的背包進行裝載。從n個物品中選取裝入背包的物品，每件物品i的重量為wi, 價值為pi。對于可行的背包裝載，背包中的物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，　　即取得最大值。約束條件 <=c和。在這個表達式中，需求出xi的值。xi=1表示物品i裝入背包中，xi

8、=0表示物品i不裝入背包。　　3、棋盤覆蓋問題　　在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個L型骨牌不得重疊覆蓋。

9、;　　二、問題分析　　1、普通背包問題　　貪心算法的基本思想是：從問題的某一個初始解出發(fā)逐步逼近給定的目標，以盡可能快的求得更好的解。當達到算法中的某一步不能再繼續(xù)前進時，算法停止。　　背包問題用貪心算法來解決，先求

10、出每件物品的平均價值即p[i]/s[i]，然后每次選擇利潤p[i]/s[i]最大的物品裝進背包，這樣就使得目標函數(shù)增加最快，當最后一種物品放不下時，選擇一個適當?shù)牟鸱?，使物品裝滿背包，使得總的價值最大。　　2、0-1背包問題　　回溯法：是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。其基本思想是在搜索嘗試中找問題的解，當

11、不滿足條件就”回溯”返回，嘗試別的路徑。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統(tǒng)搜索，逐層向其原先結點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。　　利用回溯算法來解決0-1背包，首先是將可供選擇的物品的個數(shù)輸入程序，將物品排成

12、一列，計算總物品的重量weight，然后輸入背包的實際重量weight，如果背包的重量小于0或者大于物品的總重量weight，則判斷輸入的背包重量錯誤，否則開始順序選取物品裝入背包，假設已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品"太大"不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明"剛剛"裝入背包的那件物

13、品"不合適"，應將它取出"棄之一邊"，繼續(xù)再從"它之后"的物品中選取，如此重復，直至求得滿足條件的解。 　　因為回溯求解的規(guī)則是"后進先出"，所以要用到棧來存儲符合條件的解，在存儲過程中，利用數(shù)組來存儲各個物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標存入棧里，最后得到符合條件的解并且實現(xiàn)輸出。

14、　　3、棋盤覆蓋問題　　將2^k x 2^k的棋盤，先分成相等的四塊子棋盤，其中特殊方格位于四個中的一個，構造剩下沒特殊方格三個子棋盤，將他們中的也假一個方格設為特殊方格。如果是：　　左上的子棋盤（若不存在特殊方格）則將該子棋盤右下角的那個方格假設為特殊方格；</p&g

15、t;　　右上的子棋盤（若不存在特殊方格）則將該子棋盤左下角的那個方格假設為特殊方格；　　左下的子棋盤（若不存在特殊方格）則將該子棋盤右上角的那個方格假設為特殊方格；　　右下的子棋盤（若不存在特殊方格）則將該子棋盤左上角的那個方格假設為特殊方格。　　當然上面四種，只可能且必定只有三個成立，那三

16、個假設的特殊方格剛好構成一個L型骨架，我們可以給它們作上相同的標記。這樣四個子棋盤就分別都和原來的大棋盤類似，我們就可以用遞歸算法解決。　　三、算法設計　　1、普通背包問題　　1）基本思路：</

17、p>　　首先，按物品單位價值由大到小將物品排序；(為了貪心選擇準備)　　然后，依次將單位價值大的物品放入背包（貪心選擇），直到背包放滿為止；　　在向背包放置物品的過程中，如果正在考慮裝入的物品不能全部放進去，則可以將物品的部分放入背包； 　　2）算法設計：</b

18、>　　用一維數(shù)組x[n] (x[i]∈{1,2, … ,n})，保存問題的解；weight[]存儲物品重量; price[]存儲物品價值。　　2、0-1背包問題　　1）基本思路：　?、俅_定問

19、題的解空間，并將解空間組織成易于搜索的子集樹的形式；　　圖4.1解空間樹　?、谝陨疃葍?yōu)先的方式搜索整個解空間，遇到不滿足約束要求的節(jié)點就回溯，沿另一個分支繼續(xù)搜索；約束函數(shù)剪枝，不能超載，超載就回溯。　　3、棋盤覆蓋問題

20、;　　1）問題分解過程如下：　　以k=2時的問題為例，用二分法進行分解，得到的是如下圖4-8，用雙線劃分的四個k=1的棋盤。但要注意這四個棋盤，并不都是與原問題相似且獨立的子問題。因為當如圖4-8中的殘缺方格在左上部時，第1個子問題與原問題相似，而右上角、左下角和右下角三個子棋盤（也就是圖中標識為2、3、4號子棋盤），并不是原問題的相似子問題，自然也就不能獨立求解了。當使用

21、一個①號三格板（圖中陰影）覆蓋2、3、4號三個子棋盤的各一個方格后，如4-8右圖所示，我們把覆蓋后的方格，也看作是殘缺方格（稱為“偽”殘缺方格），這時的2、3、4號子問題就是獨立且與原問題相似的子問題了。　　圖4.2 圖4.3　　從以上例子還可以發(fā)現(xiàn)，當殘缺方格在第1個子棋盤，用①號三格板覆蓋其余三個子棋盤

22、的交界方格，可以使另外三個子棋盤轉化為獨立子問題；同樣地（如下圖4-9所示），當殘缺方格在第2個子棋盤時，則首先用②號三格板進行棋盤覆蓋，當殘缺方格在第3個子棋盤時，則首先用③號三格板進行棋盤覆蓋，當殘缺方格在第4個子棋盤時，則首先用④號三格板進行棋盤覆蓋，這樣就使另外三個子棋盤轉化為獨立子問題。 　　如下圖4.4所示：<p&g

23、t;　　圖4.4　　2）棋盤的識別： 　　棋盤的規(guī)模是一個必要的信息，有了這個信息，只要知道其左上角的左上角方格所在行、列就可以唯一確定一個棋盤了，殘缺方格或“偽”殘缺方格直接用行、列號記錄。　　? tr 棋盤中左上角方格所在行。<

24、/p>　　? tc 棋盤中左上角方格所在列。　　? dr 殘缺方塊所在行。　　? dl 殘缺方塊所在列。　　? size:棋盤的行數(shù)或列數(shù)　　3）數(shù)據(jù)結構設計：

25、用二維數(shù)組board[ ][ ]，模擬棋盤。覆蓋殘缺棋盤所需要的三格板(L牌)數(shù)目為：( size2 -1 ) / 3；將這些三格板編號為1到( s i z e2-1 ) / 3。則將殘缺棋盤三格板編號的存儲在數(shù)組board[ ][ ]的對應位置中，這樣輸出數(shù)組內(nèi)容就是問題的解。結合圖4.4，理解算法。　　四、算法實現(xiàn)

26、;　　1、普通背包問題　　1）聲明變量、函數(shù)　　// 聲明變量　　int N; //物品數(shù)量　　int M;

27、 //背包容量　　double X[MAX]; //背包問題最優(yōu)解　　double Weight[MAX]; //物品重量 　　double Price[MAX]; //物品價值<

28、;p>　　double unit_price[MAX]; //物品單位價值　　double total_price; //背包總價值 　　//聲明函數(shù)　　void Input(); //輸入函數(shù)<

29、/p>　　void Mergesort(); //排序　　void knapsack(); //背包裝載　　int Output(); //結果輸出。　　2）實現(xiàn)了按照價值密度的降序排列

30、;　　void Mergesort() 　　{ 　　double temp1,temp2,temp3; 　　for(int i=1;i<N;i++)　　{

31、　　for(int j=1;j<=N-i;j++)　　{ 　　if(unit_price[j]<unit_price[j+1]) 　　{ </p&g

32、t;　　temp1=Price[j];　　Price[j]=Price[j+1];　　Price[j+1]=temp1; 　　temp2=Weight[j];　　Weight[j]=Weight[j+1];

33、;　　Weight[j+1]=temp2; 　　temp3=unit_price[j];　　unit_price[j]=unit_price[j+1];　　unit_price[j+1]=temp3; 　　} </p&g

34、t;　　}　　}　　}　　3）求最大總價值　　void knapsack()

35、　　{ 　　for( int i=1;i<=N; i++ ) //初始化X[i]，所有物品沒有放入背包　　{　　unit_price[i]=Price[i]/Weight[i]; //計算物品

36、單位價值unit_price[ ] 　　X[ i]=0; 　　} 　　double left=M; //背包剩余載重　　Mergesor

37、t(); //按單位價值將物品排序，便于貪心選擇　　while(left!=0)　　{ 　　for(int i=1;i<=N;i++) //貪心選擇，總是選擇價值最大放入背包　　{

38、 　　if(Weight[i]<=left) //當前物品小于背包剩余載重　　{ //整個放入背包　　X[i]=1; 　　left=left-Weight[i];

39、　　total_price=total_price+Price[i];　　}　　else if(Weight[i]>left) 　　{ //部分放入背包　　X[i]=left/Wei

40、ght[i]; 　　left=0; 　　total_price=total_price+Price[i]*X[i];　　}　　}&

41、lt;/p>　　}　　}　　2、0-1背包問題　　1）聲明變量、函數(shù)　　#define N

42、100 //最大物品數(shù)　　//聲明變量　　double c; //背包容量　　int n; //物品數(shù)　　double w[N]; //物品重量數(shù)組<

43、/p>　　double p[N]; //物品價值數(shù)組　　double cw; //當前重量　　double cp; //當前價值　　double bestp; //當前最優(yōu)價值　　int

44、 path[N]; //當前最優(yōu)路徑　　int x[N]; //最佳裝載　　//聲明結構體Goods　　struct Goods　　{　　double

45、 weight; //物品重量　　double price; //總價值　　int id; //物品編號　　float unit_price; //物品單位價值　　};<

46、/p>　　Goods goods[N]={{0,0,0,0}};　　//聲明函數(shù)　　void backtract(int i); //搜索解空間函數(shù)　　double bound(int i); //界限函數(shù)

47、;　　void Input(); //輸入函數(shù)　　void Output(); //輸出函數(shù)　　2) 搜索解空間函數(shù)　　//=============================搜索解空間====================<

48、;/p>　　void backtract(int i)　　{　　//到達葉節(jié)點　　if(i>=n) // i表示深度（層），i>n搜索到葉子節(jié)點&l

49、t;p>　　{　　bestp=cp;　　for(int j=0;j<n;j++)　　x[j]=path[j];　　return;

50、;　　}　　//搜索子樹　　if(cw+w[i]<=c) //當前物品放入背包不超載　　{//進入左子樹&l

51、t;p>　　cw+=w[i];　　cp+=p[i];　　path[i]=1;　　backtract(i+1); //繼續(xù)向下深度搜索　　cw-=

52、w[i];　　cp-=p[i];　　}　　//進入右子樹　　if(bound(i+1)>bestp) //當前的節(jié)點不

53、合適時，跳到下一個結點　　{　　path[i]=0;　　backtract(i+1);　　}　　}

54、;　　3）界限函數(shù)：　　//====== 限界函數(shù),計算當前價值與剩余價值和====================　　double bound(int i)　　{　　dou

55、ble cleft=c-cw; // 剩余容量　　double bound=cp; // 當前物品價值　　//以物品單位重量價值遞減的順序裝入物品　　while(i<=n&&w[i]<=cleft) // 裝載剩下的物品&

56、lt;/p>　　{　　cleft-=w[i];　　bound+=p[i];　　i++;　　} // w[ i]> cleft 跳出循環(huán)，

57、背包裝滿,物品部分裝入背包　　//裝滿背包　　if(i<=n)　　bound+=p[i]*cleft/w[i];　　return bound; // 當前物

58、品價值與剩余物品價值之和　　}　　3、棋盤覆蓋問題　　1）聲明變量：　　//聲明變量<p&

59、gt;　　int title=1; //L型骨牌號　　int board[64][64]; //二維數(shù)組board[ ][ ]，模擬棋盤　　/*　　tr 棋盤中左上角方格所在行。　　tc 棋盤中

60、左上角方格所在列。　　dr 殘缺方塊所在行。　　dl 殘缺方塊所在列。　　size:棋盤的行數(shù)或列數(shù)　　*/　　2）棋盤覆蓋分治實現(xiàn)：　　void c

61、hessBoard(int tr,int tc,int dr,int dc,int size)　　{　　int s,t;　　if(size==1) return; //size:棋盤行數(shù)

62、　　t=title++; //L型骨牌號　　s=size/2; // 分割棋盤　　// 覆蓋左上角子棋盤　　if(dr<tr+s && dc<tc+s) //特殊方格在此棋盤中<

63、/p>　　chessBoard(tr,tc,dr,dc,s);　　else // 此棋盤中無特殊方格　　{　　board[tr+s-1][tc+s-1]=t; //

64、用 t 號L型骨牌覆蓋右下角　　chessBoard(tr,tc,tr+s-1,tc+s-1,s); // 覆蓋其余方格　　}　　// 覆蓋右上角子棋盤　　if(dr<tr+s && dc>

65、=tc+s) //特殊方格在此棋盤中　　chessBoard(tr,tc+s,dr,dc,s);　　else // 此棋盤中無特殊方格　　{<p

66、>　　board[tr+s-1][tc+s]=t; // 用 t 號L型骨牌覆蓋左下角　　chessBoard(tr,tc+s,tr+s-1,tc+s,s); // 覆蓋其余方格　　}　　// 覆蓋左下角子棋盤

67、　　if(dr>=tr+s && dc<tc+s) //特殊方格在此棋盤中　　chessBoard(tr+s,tc,dr,dc,s);　　else // 此棋盤中無特殊方格&

68、lt;p>　　{　　board[tr+s][tc+s-1]=t; //用 t 號L型骨牌覆蓋右上角　　chessBoard(tr+s,tc,tr+s,tc+s-1,s); //覆蓋其余方格　　}

69、　　//覆蓋右下角子棋盤　　if(dr>=tr+s && dc>=tc+s) //特殊方格在此棋盤中　　chessBoard(tr+s,tc+s,dr,dc,s);　　else

70、 // 此棋盤中無特殊方格　　{　　board[tr+s][tc+s]=t; // 用 t 號L型骨牌覆蓋左上角　　chessBoard(tr+s,tc+s,tr+s,tc+s,s); /

71、/覆蓋其余方格　　}　　}　　五、測試分析　　1、普通背包問題　　1）、輸入物

72、品個數(shù)N=3,如圖6.1所示。　　圖6.1輸入物品數(shù)　　2）、輸入背包容量M：10，如圖6.2所示。　　圖6.2輸入背包容量　　3）、輸入各物品的大小或重量weight：6 、 5 、 5，如圖6.3所示。&l

73、t;p>　　圖6.3輸入物品重量　　4）、輸入各物品的價值p：42、25、30，如圖6.4所示。　　圖6.4輸入物品價值　　5）、顯示背包裝載結果，如圖6.5所示。　　圖6.5結果顯示&

74、lt;b>　　2、0-1背包問題　　1）、輸入背包容量：10,如圖6.6所示。　　圖6.6輸入背包容量　　2）、輸入物品個數(shù)：3，如圖6.7所示。　　圖6.7輸入物品數(shù)量　　3）、輸入各物品重量：6 、

75、5 、 5，如圖6.8所示。　　圖6.8輸入物品重量　　4）、輸入各物品的價值：42、25、30，如圖6.9所示。　　圖6.9輸入物品價值　　5）、顯示背包裝載結果，如圖6.10所示。　　圖6.10結果顯示<

76、;/b>　　3、棋盤覆蓋問題　　1）、輸入size：8，如圖6.11所示。　　圖6.11輸入棋盤大小　　2）、輸入特殊方塊的位置:4 3，如圖6.12所示。　　圖6.12輸入特殊方格位置

77、　　3）顯示棋盤覆蓋結果，如圖6.13所示。　　圖6.13結果顯示　　六、結論　　三個算法，普通背包問題是用的貪心算法設計的，0-1背包問題是用回溯算法實現(xiàn)的，棋盤覆蓋問題是用的分治法設計的。在開

78、始設計時對貪心算法和分治算法的思想很好理解，但是在設計算法時大概思路還是有的，但寫完算法寫代碼是發(fā)現(xiàn)寫不出來，原因就是算法設計的還不夠細，后來上網(wǎng)查了些資料，分析了別人的算法，最終實現(xiàn)了現(xiàn)在的算法設計。　　在最終完成的程序中：貪心算法求普通背包問題，基本上已經(jīng)實現(xiàn)了主要的功能；01背包問題也能實現(xiàn)主要功能，但一開始未使用到界限函數(shù)，后來才加上；在分治算法求棋盤覆蓋問題時，也基本上實現(xiàn)了它的功能，

79、但在輸入時還有不足，需要人工輸入2的指數(shù)冪，不夠方便。而且界面不夠友好，不能實現(xiàn)單步覆蓋。　　不過，總的來說這次實踐也是有一定收獲的，至少對書中這三個算法的知識進行了鞏固，自己更進一步地理解了這三個算法——　　貪心算法：從問題的初始解出發(fā)逐步逼近給定的目標，每一步都做出當前看來是最優(yōu)的選擇（貪心選擇），最終得到整個問題的最優(yōu)解。&

80、lt;p>　　回溯法：就是一種窮舉搜索算法。通俗地講：回溯法是一種“能進則進，進不了則換，換不了則退”的基本搜索方法。在0-1背包問題中，為了提高搜索效率，避免一些無效的搜索，則需要用限界函數(shù)bound()剪去得不到最優(yōu)解的子樹。　　分治法：分而治之。即將一個難以直接解決的大問題小規(guī)?；?，待解出子問題解之后，將子問題解合并為該問題解。<b&g

81、t;　　七、源程序　　1、普通背包問題　　#include<iostream.h> 　　#define MAX 100 //物品件數(shù)最大值　　// 聲明變量</b&

82、gt;　　int N; //物品數(shù)量　　int M; //背包容量　　double X[MAX]; //背包問題最優(yōu)解　　double Weight[MAX

83、]; //物品重量 　　double Price[MAX]; //物品價值　　double unit_price[MAX]; //物品單位價值　　double total_price; //背包總價值 <p&g

84、t;　　//聲明函數(shù)　　void Input(); //輸入函數(shù)　　void Mergesort(); //排序　　void knapsack(); //背包裝載<

85、;p>　　int Output(); //結果輸出　　//================輸入函數(shù)====================================　　void Input()　　{ <

86、p>　　int i; 　　cout<<"請輸入物體數(shù)N:";　　cin>>N;　　cout<<endl;　　cout<<&

87、quot;請輸入背包總容量M:";　　cin>>M;　　cout<<endl;　　cout<<"請輸入各物體的大小或重量weight:"<<endl;　　f

88、or(i=1;i<=N;i++)　　cin>>Weight[i];　　cout<<"請輸入各物體的價值price:"<<endl;　　for(i=1;i<=N;i++)　　cin>>Price

89、[i];　　cout<<endl;　　}　　//================按照價值密度的降序排列===================　　void Mergesort() &l

90、t;p>　　{ 　　double temp1,temp2,temp3; 　　for(int i=1;i<N;i++)　　{ 　　for(int j=1;j<=N-

91、i;j++)　　{ 　　if(unit_price[j]<unit_price[j+1]) 　　{ 　　temp1=Price[j];Price[j]=Price[j+1];Pri

92、ce[j+1]=temp1; 　　temp2=Weight[j];Weight[j]=Weight[j+1];Weight[j+1]=temp2; 　　temp3=unit_price[j];unit_price[j]=unit_price[j+1];unit_price[j+1]=temp3; <

93、;b>　　} 　　}　　}　　}　　//===============實現(xiàn)背包裝載========================

94、========　　void knapsack()　　{ 　　for( int i=1;i<=N; i++ ) //初始化X[i]，所有物品沒有放入背包　　{

95、　　unit_price[i]=Price[i]/Weight[i]; //計算物品單位價值unit_price[ ] 　　X[ i]=0; 　　} 　　double left=M;

96、 //背包剩余載重　　Mergesort(); //按單位價值將物品排序，便于貪心選擇　　while(left!=0)　　{ 　　for(int i=1;i<=N;i++) //貪心選

97、擇，總是選擇價值最大放入背包　　{ 　　if(Weight[i]<=left) //當前物品小于背包剩余載重　　{ //整個放入背包　　X[i]=1;

98、　　left=left-Weight[i]; 　　total_price=total_price+Price[i];　　}　　else if(Weight[i]>left) <p

99、>　　{ //部分放入背包　　X[i]=left/Weight[i]; 　　left=0; 　　total_price=total_price+Price[i]*X[i];　　}

100、　　}　　}　　}　　//============結果輸出======================================&l

101、t;/p>　　int Output()　　{　　char ch;　　cout<<"貪心算法實現(xiàn)背包裝載結果為:"<<endl; <p&g

102、t;　　for(int i=1;i<=N;i++) 　　{ 　　cout<<"第"<<i<<"個物體大小:"<< Weight[i]<<" 物體價值:"<< Price[

103、i]　　<<" 物體價值密度:"<< unit_price[i]<<" "<<endl; 　　}　　cout<<endl;

104、cout<<"向量表示:"<<" ( ";　　for(i=1;i<=N;i++) //輸出背包問題最優(yōu)解　　{ 　　cout<<X[i]<<&quo

105、t; "; 　　} 　　cout<<")"<<endl; 　　cout<<"背包的最優(yōu)裝載值為："<<total_price<<endl; //背包所裝

106、載總價值 　　cout<<"按Y或y繼續(xù)操作，否則按任意鍵"<<endl;　　cin>>ch;　　return ch;　　}</p&

107、gt;　　//=============主函數(shù)=========================================　　void main()　　{ 　　total_price=0;

108、　　char ch;　　while(1)　　{　　Input();　　knapsack();

109、ch=Output();　　if(ch=='Y'||ch=='y')　　continue;　　else　　break;<

110、/p>　　}　　}　　2、0-1背包問題　　#include <iostream>　　using namespace

111、std;　　#define N 100 //最大物品數(shù)　　//聲明變量　　double c; //背包容量　　int n; //物品數(shù)<p&

112、gt;　　double w[N]; //物品重量數(shù)組　　double p[N]; //物品價值數(shù)組　　double cw; //當前重量　　double cp; //當前價值　　double bestp;

113、 //當前最優(yōu)價值　　int path[N]; //當前最優(yōu)路徑　　int x[N]; //最佳裝載　　//聲明結構體Goods　　struct Goods　　{&l

114、t;/b>　　double weight; //物品重量　　double price; //總價值　　int id; //物品編號　　float unit_price; //物品單位價值

115、　　};　　Goods goods[N]={{0,0,0,0}};　　//聲明函數(shù)　　void backtract(int i); //搜索解空間函數(shù)　　double

116、 bound(int i); //界限函數(shù)　　void Input(); //輸入函數(shù)　　void Output(); //輸出函數(shù)　　//=================輸入物品數(shù)量、背包容量、各物品重量、各物品價值=============

117、==　　void Input()　　{　　int i;　　cout<<"請輸入背包容量：";　　cin&

118、gt;>c;　　cout<<"請輸入物品數(shù)量：";　　cin>>n;　　for( i=0;i<n;i++){　　printf("請輸入第%d個物品

119、的重量:\n",i+1);　　cin>>w[i];　　}　　for(i=0;i<n;i++){　　printf("請輸入第%d個物品的價值:\n",i+1);&l

120、t;p>　　cin>>p[i];　　}　　}　　//==============================輸出部分========================　　voi

121、d Output()　　{　　int i;　　printf("*******************************************************\n");<p&

122、gt;　　cout<<"最優(yōu)裝載方案是：\n";　　for(i=0;i<n;i++)　　{　　if(x[i]==1)　　{<p&

123、gt;　　cout<<"第"<<goods[i].id<<"個物品放入"<<" 價值是"<<goods[i].price<<endl;　　}　　}

124、;　　cout<<"\n最多裝載價值："<<bestp<<endl;　　}　　void knapsack()　　{&

125、lt;p>　　int i,j;　　cw=0;　　cp=0;　　bestp=0;　　for(i=0;i<n;i

126、++)　　{　　goods[i].id=i+1;　　goods[i].weight=w[i];　　goods[i].price=p[i];　　goods[i].unit_price=p[i]/

127、w[i];　　}　　//物品按單位重量從大到小排序　　for(i=0;i<n-1;i++)　　{　　for(j=0;j<n-1-i;j++)&

128、lt;/p>　　{　　if(goods[j].unit_price<goods[j+1].unit_price)　　{　　Goods temp={0,0,0,0};

129、;　　temp=goods[j];　　goods[j]=goods[j+1];　　goods[j+1]=temp;　　}　　}　　}&l

130、t;/b>　　//重新給p[]、 w[] 賦值　　for(i=0;i<n;i++)　　{　　p[i]=goods[i].price;　　w[i]=goods[i].weight;&

131、lt;/p>　　}　　//初始化當前最優(yōu)路徑　　for(i=0;i<n;i++)　　{　　path[i]=0;<b

132、>　　}　　backtract(0); //深度優(yōu)先搜索解空間　　}　　//=============================搜索解空間====================

133、　　void backtract(int i)　　{　　//到達葉節(jié)點　　if(i>=n) // i表示深度（層），i>n搜索到葉子節(jié)點<

134、;p>　　{　　bestp=cp;　　for(int j=0;j<n;j++)　　x[j]=path[j];　　return;

135、　　}　　//搜索子樹　　if(cw+w[i]<=c) //當前物品放入背包不超載　　{//進入左子樹<

136、;p>　　cw+=w[i];　　cp+=p[i];　　path[i]=1;　　backtract(i+1); //繼續(xù)向下深度搜索　　cw-=w

137、[i];　　cp-=p[i];　　}　　//進入右子樹　　if(bound(i+1)>bestp) //當前的節(jié)點不

138、合適時，跳到下一個結點　　{　　path[i]=0;　　backtract(i+1);　　}　　}

139、;　　//=========== 限界函數(shù),計算當前價值與剩余價值和==============　　double bound(int i)　　{　　double cleft=c-cw; // 剩余容量<

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

算法分析與設計課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

算法分析與設計課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載