背包問題實驗報告

1、算法設(shè)計與分析實驗報告書實驗名稱： 0/1背包問題 學(xué) 號： 姓 名： 實驗時間： 2015年 6 月 1 日 一 實驗?zāi)康暮鸵螅?） 深刻掌握貪心法、動態(tài)規(guī)劃法、回溯法的設(shè)計思想并能熟練運用（2） 理解這樣一個觀點：同樣的問題可以用不同的方法來解決，一個好的算法是反復(fù)努力和重新修正的結(jié)果。 二 實驗內(nèi)容（1）分別用蠻力法貪心法、動態(tài)規(guī)劃法、回溯法設(shè)計0/1背包問題的算法。（2）分析算法隨n和C變化的時間性能，隨機產(chǎn)生參數(shù)n和C，收集算法執(zhí)行的時間（3）討論n和C變化時，動態(tài)規(guī)劃法和回溯法的時間性能。（4）討論幾種算法在該問題求解上的特點。三 實驗環(huán)境 VC+6.0四 設(shè)計思想及實驗步驟 蠻

2、力法的設(shè)計思想和步驟將所有排列下的背包的重量和價值都計算出來，選擇重量不大于背包的總重量下的最大價值。貪心法的設(shè)計思想和步驟首先計算每種物品單位重量的價值vi/wi；按單位價值對物品進行升序排列。然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包，直到背包裝滿為止。動態(tài)規(guī)劃法的設(shè)計思想和步驟令V(i, j)表示在前i個物品中能夠裝入容量為j的背包中的物品的最大價值，則可以得到如下動態(tài)函數(shù)：V（i, j）=0 (i=0或j=0)V( i, j) = V(i-1, j) j=wj按照下述方法來劃分段：第一段只裝入前1個物品，確定在各種情況下的背包能夠得到的最大價值；第二階段，只裝入2

3、個物品，確定在各種情況下的背包能夠得到的最大價值；以此類推，直到第n個階段。最后V(n, C)便是容量為C的背包中裝入n個物品時獲取到的最大價值?；厮莘ǖ脑O(shè)計思想和步驟為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài)，要不斷的利用越約束條件來剪掉那些實際上不可能產(chǎn)生所需解的節(jié)點，以減少問題額計算量。對于n種可選物品的0/1背包問題，其解空間長度由長度為n的0-1向量組成，可用子集數(shù)表示。在搜索解空間樹時，只要其左兒子節(jié)點是一個可行節(jié)點，搜索進入左子樹，否則返回上一節(jié)點，搜索右子數(shù)。時間測試的設(shè)計思想蠻力法由于需要考慮每一種情況所以物品的個數(shù)不能太多，所以設(shè)計時間測試函數(shù)在1到32的范圍內(nèi)隨機殘生物品

4、的個數(shù)n，然后在隨機產(chǎn)生n個物品每個物品的重量和價值，將背包容量設(shè)為n個物品總重量的一半，求出最優(yōu)解。重復(fù)執(zhí)行背包求解過程，然后求出其平均時間消耗。算法描述如下：蠻力法：輸入：物品總數(shù)n，每個物品的重量wi和價值vi，背包容量C輸出：背包所裝物品的最大總價值1. 求出2的n次方2. 循環(huán)i從1到m-1，2.1 求出i的二進制2.2 根據(jù)i的二進制序列，判斷重量和是否小于或等于C，如果等于則求出總價值value，2.3 如果valuemaxValue, 則maxValue=value;，并把該二進制序列T復(fù)制到S數(shù)組中以記錄最優(yōu)解。貪心法：輸入：物品總數(shù)n，每個物品的重量wi和價值vi，背包容量

5、C輸出：背包所裝物品的最大總價值1. 將每個物品的重量和價值存放到保存物品信息的結(jié)構(gòu)體node中2. 將node數(shù)組中的物品暗中單位價值的大小從大到小排序3. Temp=C;4. 循環(huán)i從1到n如果nodei.w=temp，將物品放入背包，標記nodei=1; temp-=nodei.w; i+;如果temp=0背包被裝滿，結(jié)束循環(huán)。動態(tài)規(guī)劃法輸入：物品總數(shù)n，每個物品的重量wi和價值vi，背包容量C輸出：背包所裝物品的最大總價值1. 初始化過程圖2. 雙重循環(huán)，逐步求出將前i個物品放到容量為j的背包獲得的最大價值 for(i=1;i=n;i+) for(j=1;j=C;j+)如果j0;i-)

6、如果VijVi-1j， 則xi=1;j=j-wi;否則 xi=0;回溯法（遞歸）輸入：物品總數(shù)n，每個物品的重量wi和價值vi，背包容量C輸出：背包所裝物品的最大總價值1. 從第一個物品開始,t=1;2. 如果legal(t)=1,則backTrack（t+1）分析下一個物品3. 如果tn，求出背包的總價值value，如果value大于最大價值，則把最大價值更新，同時更新記錄物品裝入情況的數(shù)組P, 以記錄最優(yōu)解。六 核心源代碼 #include#include#include#include#include#includeusing namespace std;int w505, v505,n

7、;long C;/回溯法int p500,P500;/回溯法中分別記錄當前解和最優(yōu)解的狀態(tài)數(shù)組int Value=0;/回溯法中的最大價值bool legal(int t) int sum=0; for(int i=1;iC) return false; else return true;void backTrack(int t) if(tn) int i; int value=0; for(i=1;i=n;i+) value+=vi*pi; /coutValue) Value=value; for(i=1;i=0;i-) pt=i; if(legal(t) backTrack(t+1); i

8、nt Back() backTrack(1); return Value;/動態(tài)規(guī)劃法int Max(int a,int b) return ab?a:b;int KnapSack()/動態(tài)規(guī)劃法int V505505;int x1005;int i,j;for(i=0;i=n;i+)/初始化第0列Vi0=0;for(j=0;j=C;j+)V0j=0;/初始化第0行for(i=1;i=n;i+)for(j=1;j=C;j+)if(j0;i-)if(VijVi-1j)xi=1;j=j-wi;else xi=0; return VnC;/蠻力法int Force()/蠻力法int maxValue

9、=0;int m=1n;int S32,T32;for(int i=1;im;i+)int t=1;int temp=i;while(temp)Tt+=temp%2;temp=temp/2;int j;/*for(j=1;jt;j+) coutTj;*/int weight=0,value=0;for(j=1;jt;j+)if(Tj=1 & weight+wj=C )weight=weight+wj;value=value+vj;if(maxValuevalue)maxValue=value;int k=0;for(j=0;j(b.v/b.w);int greed() int i; int m

10、axValue=0; for(i=1;i=n;i+) nodei.i=0; nodei.w=wi; nodei.v=vi; sort(node+1,node+n+1,cmp); /*for(i=1;i=n;i+) coutnodei.w nodei.vendl; */ int temp=C; i=1; while(temp & (i=n) if(nodei.w=temp) maxValue+=nodei.v; nodei.i=1; temp-=nodei.w; / coutnodei.w ; i+; return maxValue;int Random() return (rand()%(10

11、00)+1);void text(int (*matter)() LARGE_INTEGER litmp;LONGLONG start,over;double dfMinus,dfFreq,dfTim; QueryPerformanceFrequency(&litmp); dfFreq=(double)litmp.QuadPart; QueryPerformanceCounter(&litmp); start=litmp.QuadPart;for(int k=0;k100;k+) C=0; n=Random()%30; for(int i=1;i=n;i+) wi=Random(); vi=R

12、andom(); C=C+wi; C=C/2; matter(); /coutmatter()endl; QueryPerformanceCounter(&litmp); over=litmp.QuadPart; dfMinus=(double)(over-start); dfTim=dfMinus/dfFreq/100; cout平均時間T(k): ; printf(%et,dfTim); coutendl;int main()cout先測試算法的正確性endl;n=4;C=10;w1=7;w2=3;w3=4;w4=5;v1=42;v2=12;v3=40;v4=25;cout蠻力法Force

13、()endl;cout貪心法greed()endl;cout動態(tài)規(guī)劃法KnapSack()endl;cout回溯法Back()endl;cout測試時間效率：endl;srand(unsigned)time(NULL);cout動態(tài)規(guī)劃法的執(zhí)行時間：endl;cout蠻力法的執(zhí)行時間：endl;text(Force);cout貪心法的執(zhí)行時間endl;text(greed);cout動態(tài)規(guī)劃法的執(zhí)行時間endl;text(KnapSack);cout回溯法的執(zhí)行時間endl; text(Back);return 0;七 實驗結(jié)果及分析下面的結(jié)果是每個算法都分別運行50次后的平均運行時間：根據(jù)結(jié)

14、果可以得出，蠻力算法的效率是最低的，回溯算法的時間效率優(yōu)勢很明顯是最高的，而貪心法和動態(tài)規(guī)劃的效率也均高于蠻力法，且二者相差不明顯。蠻力法時間復(fù)雜性分析：對于n個元素的集合，其子集數(shù)量時2n,所以不論生成子集的算法效率有多高，蠻力法求接0/1背包問題都會導(dǎo)致一個下界為2n的算法。蠻力法的特點：蠻力法是一種簡單直接的解決問題的方法，常常直接基于問題的描述和所涉及的概念定義。貪心法時間復(fù)雜性分析：貪心法首選對物品進行了排序，按照價值/重量將序排列，此處采用的是快速排序，時間復(fù)雜性為O(nlogn);然后按照物品的大小依次裝入背包中，其時間復(fù)雜性我O(n),故總的時間復(fù)雜性為O(nlogn)。貪心法

15、的特點：貪心法的貪心策略需要滿足最優(yōu)子結(jié)構(gòu)性質(zhì)和整體貪心選擇性質(zhì)。在o/1背包問題中，選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡，作為貪心策略滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。動態(tài)規(guī)劃法的時間復(fù)雜性分析：動態(tài)規(guī)劃法的算法中第一個for循環(huán)的時間性能是O(n), 第二個for循環(huán)的時間性能是O(C),第三個for循環(huán)是兩層嵌套的for循環(huán)其時間性能是O(n*C),算法的時間復(fù)雜性是O(n*C)；動態(tài)規(guī)劃法的特點：動態(tài)規(guī)劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應(yīng)決策過程的一個階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動態(tài)規(guī)劃函數(shù)）中，將

16、子問題的解求解一次并填入表中，下次需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計算。回溯法的時間復(fù)雜性分析：回溯法實質(zhì)上是蠻力窮舉法，所以最不理想的情況下，回溯法求解0/1背包問題的時間復(fù)雜度為O(2n).在求0/1背包問題中，回溯法做到了很好的剪枝，減少了運算量，所以雖然回溯法本質(zhì)上是蠻力窮舉法，因為減去了很多情況的分析，在時間效率上有很大的優(yōu)勢。八 實驗體會（包括本實驗中遇到的問題、具體的解決方法、還沒有解決的問題、實驗收獲等）1. 開始時沒有設(shè)置隨機種子，導(dǎo)致每次運行測試的數(shù)據(jù)一樣，后來看了下書知道了問題所在。2. 貪心算法還有點問題，對于物品中存在若干個單位價值相同的物品時，可能得到的最優(yōu)解是不正確的。例如：w1=3;w2=2;w3=1;w4=4;w5=5;v1=25;v2=20;v3=15;v4=40;v5=50;在物品重量及價值如上時，貪心法得到的最優(yōu)解是60，但是其他三個算法的得到的最優(yōu)解均是65，可見貪心法得到的結(jié)果是不正確的。3. 蠻力法的時間復(fù)雜度是O（2n），其形成的二進制序列與物品的個數(shù)有關(guān)，整形的長度只有32位，所以只有在物品的個數(shù)不超過32個才能用二進制序列一一表示，因為這個緣故我在時間效率測試函數(shù)中，將物品個