算法導(dǎo)論課程設(shè)計---背包問題

1、<p>　　課 程 設(shè) 計 報 告</p><p>　　課程名稱 算法導(dǎo)論 </p><p>　　課題名稱 0-1背包問題 </p><p>　　專 業(yè) 信息與計算科學(xué) </p><p>　　班 級

2、 </p><p>　　學(xué) 號 </p><p>　　姓 名 </p><p>　　指導(dǎo)教師 </p><p>　　2011年 12 月 26 日</p><p>　　

3、一、設(shè)計內(nèi)容與設(shè)計要求</p><p><b>　　1．設(shè)計內(nèi)容：</b></p><p>　　對課程《算法導(dǎo)論》中的常用算法進(jìn)行綜合設(shè)計或應(yīng)用（具體課題題目見后面的供選題目）。</p><p><b>　　2．設(shè)計要求：</b></p><p>　　課程設(shè)計報告正文內(nèi)容</p>&l

4、t;p><b>　　(一)問題的描述；</b></p><p>　　(二)算法設(shè)計與分析，內(nèi)容包括</p><p>　　1， 算法設(shè)計，對問題的分析和算法的設(shè)計</p><p>　　2，算法描述，以偽代碼形式的算法</p><p>　　3，算法分析，主要是算法的正確性和運行時間的分析</p><

5、p><b>　?。ㄈ┧惴▽崿F(xiàn)</b></p><p>　　所有程序的原代碼，要求用C語言程序?qū)崿F(xiàn)，并對程序?qū)懗霰匾淖⑨尅?lt;/p><p><b>　　書寫格式</b></p><p>　　a．要求用A4紙打印成冊</p><p>　　b．正文格式：一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗

6、,正文用小四號宋體;行距為22。</p><p>　　c．正文的內(nèi)容:正文總字?jǐn)?shù)要求在3000字左右（不含程序原代碼）。</p><p>　　d．封面格式如下頁。</p><p><b>　　考核方式</b></p><p>　　指導(dǎo)老師負(fù)責(zé)驗收程序的運行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設(shè)計報告等進(jìn)行

7、綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學(xué)的課程設(shè)計成績。具體考核標(biāo)準(zhǔn)包含以下幾個部分：</p><p>　　a．平時出勤 （占10%）</p><p>　　b．系統(tǒng)需求分析、功能設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計及程序總體結(jié)構(gòu)合理與否（占10%）</p><p>　　c．程序能否完整、準(zhǔn)確地運行，個人能否獨立、熟練地調(diào)試程序（占40%）</p>

8、<p>　　d．設(shè)計報告（占30%）</p><p>　　e．獨立完成情況（占10%）。</p><p>　　注意：不得抄襲他人的報告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧?lt;/p><p><b>　　課程驗收要求</b></p><p>　　a．判定算法設(shè)計的合理性，運行相關(guān)程序，獲得正確的數(shù)值結(jié)果。&l

9、t;/p><p><b>　　b．回答有關(guān)問題。</b></p><p>　　c．提交課程設(shè)計報告。</p><p>　　d．提交軟盤（源程序、設(shè)計報告文檔）。</p><p>　　e．依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。</p><p><b>　　三、進(jìn)度安排</b

10、></p><p>　　班級： 信息與計算科學(xué)：0901、0902、0903</p><p><b>　　主講教師： </b></p><p><b>　　時間安排：</b></p><p>　　第 16 周 星期一 8時：30分——11時：30分</p><p>

11、　　星期二 8時：30分——11時：30分</p><p>　　星期四 8時：30分——11時：30分</p><p>　　星期五 8時：30分——11時：30分</p><p><b>　　目錄</b></p><p>　　1.封面………………………………………………………………………1</p><

12、;p>　　2.任務(wù)書……………………………………………………………………2</p><p>　　2.目錄………………………………………………………………………5</p><p>　　正文………………………………………………………………………6</p><p>　　4.附件………………………………………………………………………10</p><

13、p>　　5.評分表……………………………………………………………………13</p><p><b>　　一、設(shè)計內(nèi)容</b></p><p>　　0-1背包問題：有N件物品和一個容量為V的背包。第i件物品的重量是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。 </p><p>　　利

14、用動態(tài)規(guī)劃的方法解決0-1背包問題。</p><p><b>　　問題分析</b></p><p>　　背包問題(Knapsack problem)是一種組合優(yōu)化的NP完全問題。問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商

15、業(yè)、組合數(shù)學(xué)，計算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。也可以將背包問題描述為決定性問題，即在總重量不超過W的前提下，總價值是否能達(dá)到V？它是在1978年由Merkel和Hellman提出的。 </p><p>　　1、0-1背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)</p><p>　　證明：因為，若(z2, ··· zn )是下述子問題的一個最優(yōu)解，而（y2, ·

16、;·· yn）不是它的最優(yōu)解:</p><p><b>　　則</b></p><p><b>　　因此</b></p><p>　　這說明(y1,z2, ··· zn )是所給問題的一個更優(yōu)解，從而(y1, y2,··· yn )不是原問題的

17、最優(yōu)解，矛盾。</p><p><b>　　2、基本思路</b></p><p>　　這是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。　　用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。 可以壓縮空

18、間，f[v]=max{f[v],f[v-c[i]]+w[i]}　　</p><p>　　這個方程非常重要，基本上所有跟背包相關(guān)的問題的方程都是由它衍生出來的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][

19、v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。</p><p>　　注意f[v]有意義當(dāng)且僅當(dāng)存在一個前i件物品的子集，其費用總和為v。所以按照這個方程遞推完畢后，最終的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果將狀態(tài)的定義中的“恰”字去掉

20、，在轉(zhuǎn)移方程中就要再加入一項f[v-1]，這樣就可以保證f[N] [V]就是最后的答案。 </p><p><b>　　3、優(yōu)化空間復(fù)雜度</b></p><p>　　以上方法的時間和空間復(fù)雜度均為O(N*V)，其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(N)。</p><p>　　先考慮上面講的基本思路如何實現(xiàn)，肯定是有一

21、個主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個數(shù)組f [0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？　</p><p>　　f[i][v]是由f[i-1][v]和f [i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[v]和f[v -c[i]]的值呢？事實上，這要

22、求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值。偽代碼如下：</p><p>　　for i=1..N　</p><p>　　for v=V..0　　</p><p>　　f[v]=max{f[v],f[v-c[i]]+w[i]};　</p><p>

23、　　其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現(xiàn)在的</p><p>　　f[v-c[i]]就相當(dāng)于原來的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決

24、方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。 </p><p><b>　　三、程序調(diào)試</b></p><p><b>　　1、運行結(jié)果預(yù)覽</b></p><p><b>　　四、總結(jié)</b></p><p>　　0/1背包問題是最基本的背包問題，它包含了背包問題中

25、設(shè)計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成0/1背包問題求解。故一定要仔細(xì)體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。 </p><p><b>　　五、心得</b></p><p>　　一周的課程設(shè)計結(jié)束了，在這次的課程設(shè)計中不僅檢驗了我所學(xué)習(xí)的知識也培養(yǎng)了我如何去把握一件事情，如何去做一件事情，又如何完成

26、一件事情。在設(shè)計過程中，與同學(xué)分工設(shè)計，和同學(xué)們相互探討，相互學(xué)習(xí)，相互監(jiān)督。</p><p>　　課程設(shè)計是我們專業(yè)課程知識綜合應(yīng)用的實踐訓(xùn)練，這是我們邁向社會從事職業(yè)工作前一個必不少的過程．”千里之行始于足下”，通過這次課程設(shè)計，我深深體會到這句千古名言的真正含義．我今天認(rèn)真的進(jìn)行課程設(shè)計，學(xué)會腳踏實地邁開這一步，就是為明天能穩(wěn)健地在社會大潮中奔跑打下堅實的基礎(chǔ)．</p><p>　　

27、在這次設(shè)計過程中，體現(xiàn)出自己單獨設(shè)計程序的能力以及綜合運用知識的能力，體會了學(xué)以致用、突出自己勞動成果的喜悅心情，從中發(fā)現(xiàn)自己平時學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補。</p><p>　　在此感謝我們的xx老師，你嚴(yán)謹(jǐn)細(xì)致、一絲不茍的作風(fēng)一直是我們工作、學(xué)習(xí)中的榜樣；你開朗的個性和寬容的態(tài)度，幫助我能夠很順利的完成了這次課程設(shè)計。</p><p><b>　　附件</b&g

28、t;</p><p><b>　　1、程序代碼</b></p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#include <conio.h></p><p>　　#incl

29、ude <malloc.h></p><p>　　#include <windows.h></p><p>　　typedef struct goods</p><p><b>　　{</b></p><p>　　double *value; //價值</p><p>　　

30、double *weight; //重量</p><p>　　char *select; //是否選中到方案 </p><p>　　int num;//物品數(shù)量 </p><p>　　double limitw; //限制重量</p><p><b>　　}GOODS;</b></p><p>　

31、　double maxvalue,totalvalue;//方案最大價值,物品總價值 </p><p>　　char *select1; //臨時數(shù)組 </p><p>　　void backpack(GOODS *g, int i, double tw, double tv)//參數(shù)為物品i,當(dāng)前選擇已經(jīng)達(dá)到的重量和tw,本方案可能達(dá)到的總價值 </p><p>

32、<b>　　{</b></p><p><b>　　int k;</b></p><p>　　if (tw + g->weight[i] <= g->limitw)//將物品i包含在當(dāng)前方案,且重量小于等于限制重量 </p><p><b>　　{</b></p>&l

33、t;p>　　select1[i] = 1; //選中第i個物品 </p><p>　　if (i < g->num - 1) //若物品i不是最后一個物品 </p><p>　　backpack(g, i + 1, tw + g->weight[i], tv); //遞歸調(diào)用,繼續(xù)添加下一物品 </p><p>　　else //若已到最后一

34、個物品 </p><p><b>　　{</b></p><p>　　for (k = 0; k < g->num; ++k) //將狀態(tài)標(biāo)志復(fù)制到option數(shù)組中 </p><p>　　g->select[k] = select1[k];</p><p>　　maxvalue = tv; //保存當(dāng)

35、前方案的最大價值 </p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　select1[i] = 0; //取消物品i的選擇狀態(tài) </p><p>　　if (tv - g->value[i] > maxvalue)//若物品總價值減去物品

36、i的價值還大于maxv方案中已有的價值,說明還可以繼續(xù)向方案中添加物品 </p><p><b>　　{</b></p><p>　　if (i < g->num - 1) //若物品i不是最后一個物品 </p><p>　　backpack(g, i + 1, tw, tv - g->value[i]); //遞歸調(diào)用,繼續(xù)

37、加入下一物品 </p><p>　　else //若已到最后一個物品 </p><p><b>　　{</b></p><p>　　for (k = 0; k < g->num; ++k) //將狀態(tài)標(biāo)志復(fù)制到option數(shù)組中 </p><p>　　g->select[k] = select1[k];

38、</p><p>　　maxvalue = tv - g->value[i]; //保存當(dāng)前方案的最大價值(從物品總價值中減去物品i的價值)</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p

39、><p>　　int main()</p><p><b>　　{</b></p><p>　　double sumweight;</p><p><b>　　GOODS g;</b></p><p><b>　　int i;</b></p>

40、<p>　　printf("背包最大重量:");</p><p>　　scanf("%lf",&g.limitw);</p><p>　　printf("可選物品數(shù)量:"); </p><p>　　scanf("%d",&g.num);</p>&

41、lt;p>　　if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配內(nèi)存保存物品價值 </p><p><b>　　{</b></p><p>　　printf("內(nèi)存分配失敗\n");</p><p><b>　　exit(0); </b

42、></p><p><b>　　}</b></p><p>　　if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配內(nèi)存保存物品的重量 </p><p><b>　　{</b></p><p>　　printf("內(nèi)

43、存分配失敗\n");</p><p>　　exit(0); </p><p><b>　　}</b></p><p>　　if(!(g.select = (char *)malloc(sizeof(char)*g.num)))//分配內(nèi)存保存物品的重量 </p><p><b>　　{</b

44、></p><p>　　printf("內(nèi)存分配失敗\n");</p><p>　　exit(0); </p><p><b>　　}</b></p><p>　　if(!(select1 = (char *)malloc(sizeof(char)*g.num)))//分配內(nèi)存保存物品的重量

45、 </p><p><b>　　{</b></p><p>　　printf("內(nèi)存分配失敗\n");</p><p>　　exit(0); </p><p><b>　　}</b></p><p>　　totalvalue=0; </p&g

46、t;<p>　　for (i = 0; i < g.num; i++)</p><p><b>　　{</b></p><p>　　printf("輸入第%d號物品的重量和價值:",i + 1);</p><p>　　scanf("%lf%lf",&g.weight[i],&a

47、mp;g.value[i]);</p><p>　　totalvalue+=g.value[i];//統(tǒng)計所有物品的價值總和 </p><p><b>　　}</b></p><p>　　printf("\n背包最大能裝的重量為:%.2f\n\n",g.limitw); </p><p>　　for

48、(i = 0; i < g.num; i++)</p><p>　　printf("第%d號物品重:%.2f,價值:%.2f\n", i + 1, g.weight[i], g.value[i]); </p><p>　　for (i = 0; i < g.num; i++)//初始設(shè)各物品都沒加入選擇集 </p><p>　　se

49、lect1[i]=0;</p><p>　　maxvalue=0;//加入方案物品的總價值 </p><p>　　backpack(&g,0,0.0,totalvalue); //第0號物品加入方案,總重量為0,所有物品價值為totalvalue </p><p>　　sumweight=0; </p><p>　　printf(&q

50、uot;\n可將以下物品裝入背包,使背包裝的物品價值最大:\n"); </p><p>　　for (i = 0; i < g.num; ++i)</p><p>　　if (g.select[i])</p><p><b>　　{</b></p><p>　　printf("第%d號物品,重量

51、:%.2f,價值:%.2f\n", i + 1, g.weight[i], g.value[i]); </p><p>　　sumweight+=g.weight[i];</p><p><b>　　} </b></p><p>　　printf("\n總重量為: %.2f,總價值為:%.2f\n", sumw

52、eight, maxvalue ); </p><p><b>　　getch();</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　2、參考書籍</b></p&g