1、西安郵電學(xué)院算法設(shè)計與分析課內(nèi)試驗報告題 目： 0-1 背包 ( 動態(tài)規(guī)劃、回溯 ) 和背包 ( 貪心 )院系名稱：計算機(jī)學(xué)院專業(yè)名稱：軟件工程專業(yè)班 級： 0903 班學(xué)生姓名：張橋?qū)W號（ 8 位）： 04095091(23)指導(dǎo)教師：陳琳時間：2011 年 12 月一. 設(shè)計目的通過上機(jī)實驗：深刻理解和掌握 0-1 背包 ( 動態(tài)規(guī)劃算法、 回溯算法 ) 和背包 ( 貪心算法 ) 的問題描述、算法設(shè)計思想、程序設(shè)計、算法復(fù)雜性分析、他們的區(qū)別及聯(lián)系。二. 設(shè)計內(nèi)容1 問題的描述(1)0-1 背包問題給定 n 種物品和一背包。 物品 i 的重量是 wi，其價值為 vi ，背包的容量為 c。問

2、應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大(2) 背包問題與 0-1 背包問題類似，所不同的是在選擇物品 i 裝入背包時，可以選擇物品 i 的一部分，而不一定要全部裝入背包，1=i=n。2 算法設(shè)計思想(1)0-1 背包問題動態(tài)規(guī)劃法：是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解， 為后一子問題的求解提供了有用的信息。v n j w n 在求解任一子問m ( n , j )題時，列出各種可能的局部解， 通過決策保留那些有可能達(dá)到最優(yōu)的局部解，0 0 j w n丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。m ( i 由于動態(tài)規(guī)

3、劃解決的問題多數(shù)有重疊子問題這個特點(diǎn)，, j ) max m ( i ,1 j ), m ( i ,1 j w ) 為減少重復(fù)計算， 對 v j w每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。m ( i ,1 j ) 0 j wi設(shè)所給 0-1 背包問題的子問題的最優(yōu)值為m(i ，j) ，即 m(i ，j) 是背包容量為 j ，可選擇物品為 i ，i+1 ， ， n 時 0-1 背包問題的最優(yōu)值。由 0-1 背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i ，j) 的遞歸式如下?；厮莘ǎ涸趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)

4、時，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。(2) 背包問題貪心算法：首先計算每種物品單位重量的價值Vi/Wi ，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。三測試數(shù)據(jù)及運(yùn)行結(jié)果1正常測試數(shù)據(jù)（ 3 組）及運(yùn)行結(jié)果 0-1 背包問題：動態(tài)規(guī)劃法：回溯法：背包問題：貪心算法：四調(diào)試情況，設(shè)計技巧及體會本次的實驗大體理解和掌握0-

5、1 背包 ( 動態(tài)規(guī)劃算法、回溯算法 ) 和背包 ( 貪心算法 ) 的問題描述、算法設(shè)計思想、程序設(shè)計、算法復(fù)雜性分析、他們的區(qū)別 及聯(lián)系。通過本次上機(jī)實驗，我對0-1 背包 ( 動態(tài)規(guī)劃算法、回溯算法) 和背包 ( 貪心算法 ) 有了更為深刻的了解，利用動態(tài)規(guī)劃算法、回溯算法和貪心可以將問題簡 化，這有助于我們在實際問題中解決一些復(fù)雜性較大的問題，提高程序的運(yùn)行效率。但要注意他們的區(qū)別與不同的應(yīng)用場景。五. 源代碼 1）0-1 背包：動態(tài)規(guī)劃法：#include #define MAX 20void Knapsack(int *value, int *weight, int column,

6、int length, int (*middle)MAX);void TraceBack(int (*middle)MAX, int *weight, int column, int length, int *x); int Max(int x, int y); int Min(int x, int y);int Min(int x, int y) return x = y x : y; void TraceBack(int (*middle)MAX, int *weight, int column, int length, int *x) int i;for(i = 1; i length;

7、 i+) if(middleicolumn = middlei + 1column) xi = 0;else xi = 1; column -= weighti; xlength = (middlelengthcolumn 1 : 0); void Knapsack(int *value, int *weight, int column, int length, int (*middle)MAX) int i, j, jMax = Min(weightlength - 1, column);for(j = 0; j = jMax; j+) middlelengthj = 0;for(j = w

8、eightlength; j 1; i-) jMax = Min(weighti - 1, column);for(j = 0; j = jMax; j+) middleij = middlei + 1j;for(j = weighti; j = weight1)middle1column = Max(middle1column, middle2column - weight1 + value1); void main(void) int i, length, column, count = 0, weightMAX, valueMAX, xMAX = 0, middleMAXMAX = 0;

9、printf(請輸入背包總?cè)萘浚簄);scanf(%d, &column);printf(請輸入物品個數(shù)：n);scanf(%d, &length);if(length 1) printf( 輸入錯誤！n); return; for(i = 1; i = length; i+) printf(請輸入第 %d個物品的重量及價值：n, i);scanf(%d %d, weight + i, value + i); Knapsack(value, weight, column, length, middle); TraceBack(middle, weight, column, length, x)

10、;printf(Result:n); for(i = 1; i = length; i+) if(xi)printf(Number: %d, , i); printf(n); 回溯法：#include #include #include typedef struct goods int num; double *value; double *weight; int *location; double column; double currentWeight; double currentValue; double bestValue; GOODS;void Knapsack(GOODS *go

11、ods, int i); double Bound(GOODS *goods, int i); void SwapDouble(double *m, double *n); void SwapInt(int *m, int *n); void Sort(GOODS *goods);void Sort(GOODS *goods) int i, j; double *temp;temp = (double *)malloc(sizeof(goods - num + 1); for(i = 1; i num; i+) tempi = goods - valuei / goods - weighti;

12、for(i = 1; i num; i+) for(j = i + 1; j num; j+) if(tempi weighti, &goods - weightj); SwapDouble(&goods - valuei, &goods - valuej); SwapInt(&goods - locationi, &goods - locationj); void SwapInt(int *m, int *n) int temp;temp = *m; *m = *n;*n = temp; void SwapDouble(double *m, double *n) double temp;te

13、mp = *m; *m = *n; *n = temp; double Bound(GOODS *goods, int i) double leftWeight = goods - column - goods - currentWeight; double bound = goods - currentValue;while(i num & goods - weighti weighti; bound += goods - valuei; i+; if(i num) bound += goods - valuei * leftWeight / goods - weighti;return b

14、ound; void Knapsack(GOODS *goods, int i) if(i goods - num) goods - bestValue = goods - currentValue; return; if(goods - currentWeight + goods - weighti column) goods - locationi = 1; goods - currentWeight += goods - weighti; goods - currentValue += goods - valuei; Knapsack(goods, i + 1); goods - cur

15、rentWeight -= goods - weighti; goods - currentValue -= goods - valuei; if(Bound(goods, i + 1) goods - bestValue) goods - locationi = 0; Knapsack(goods, i + 1); void main(void) int i;double totalValue, totalWeight, sumWeight; GOODS *goods = NULL;totalValue = totalWeight = sumWeight = ;if(!(goods = (G

16、OODS *)malloc(sizeof(GOODS) printf( 內(nèi)存分配失敗 n); exit(0); goods - currentValue = goods - currentWeight = goods - bestValue = ;printf( 請輸入背包最大重量 :n); scanf(%lf, &goods - column); printf( 請輸入可選物品數(shù)量 :n); scanf(%d, &goods - num);if(!(goods - value = (double *)malloc(sizeof(double) * (goods - num + 1) prin

17、tf( 內(nèi)存分配失敗 n); exit(0); if(!(goods - weight = (double *)malloc(sizeof(double) * (goods - num + 1) printf( 內(nèi)存分配失敗 n);exit(0); if(!(goods - location = (int *)malloc(sizeof(int) * (goods - num + 1) printf( 內(nèi)存分配失敗 n); exit(0); for(i = 1; i num; i+) goods - locationi = 0;for(i = 1; i num; i+) printf( 輸入第

18、 %d號物品的重量和價值 :n, i); scanf(%lf %lf, &goods - weighti, &goods - valuei); totalValue += goods - valuei; totalWeight += goods - weighti; Sort(goods);printf(n 排序后的物品內(nèi)容如下：n); printf(n 背包最大能裝的重量為 : %.2lfnn,goods - column); for(i = 1; i num; i+)printf(第 %d 號 物 品 重 : %.2lf,價 值 : %.2lfn, i, goods - weighti,

19、goods - valuei);printf(n所有物品總重量為：%.2lf ，總價值為 : %.2lfnn, totalWeight, totalValue);Knapsack(goods, 1);printf(n可將以下物品裝入背包 , 使背包裝的物品價值最大:n);for (i = 1; i num; i+) if(goods - locationi) printf(第%d號物品 , 重量: %.2lf, 價值 : %.2lfn, i, goods - weighti, goods - valuei); sumWeight += goods - weighti; printf(n背包中物

20、品最大重量為: %.2lf, 最大價值為: %.2lfn, sumWeight, goods - bestValue); 2）背包問題：貪心算法：#include #define MAX 10void Knapsack(int *value, int *weight, int column, int length, double (*middle)MAX); void Sort(double (*middle)MAX, int length); void Swap(double *m, double *n);void Swap(double *m, double *n) double temp

21、;temp = *m; *m = *n; *n = temp; void Sort(double (*middle)MAX, int length) int i, j;for(i = 0; i length - 1; i+) for(j = i + 1; j length; j+) if(middle1i middle1j) Swap(&middle0j, &middle0i); Swap(&middle1j, &middle1i); void Knapsack(int *value, int *weight, int column, int length, double (*middle)MAX) int i, leftColumn = column, temp;for(i