0-1背包動(dòng)態(tài)規(guī)劃、回溯和背包貪心試驗(yàn)報(bào)告

1、西安垂院算法設(shè)計(jì)與分析課內(nèi)試驗(yàn)報(bào)告題 目：0-1背包動(dòng)態(tài)規(guī)劃、回溯和背包貪心院系名稱：計(jì)算機(jī)學(xué)院專業(yè)名稱：軟件工程專業(yè)班 級(jí)： 0903 班學(xué)生姓名：1W學(xué)號(hào)8 位:0409509123指導(dǎo)教師：W時(shí)間：2021年12月一.設(shè)計(jì)目的通過(guò)上機(jī)實(shí)驗(yàn)：深刻理解和掌握0-1背包(動(dòng)態(tài)規(guī)劃算法、回溯算法)和背包(貪心算法)的問(wèn) 題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)、算法復(fù)雜性分析、他們的區(qū)別及聯(lián)系.二.設(shè)計(jì)內(nèi)容1問(wèn)題的描述(1)0-1背包問(wèn)題給定n種物品和一背包.物品i的重量是wi,其價(jià)值為vi ,背包的容量為c 問(wèn)應(yīng)如何選擇裝入背包中的物品,使得裝入背包中物品的總價(jià)值最大(2)背包問(wèn)題與0-1背包問(wèn)題類似,

2、所不同的是在選擇物品i裝入背包時(shí), 可以選擇物品i的一局部,而不一定要全部裝入背包,1<=i<=n.2算法設(shè)計(jì)思想(1)0-1背包問(wèn)題動(dòng)態(tài)規(guī)劃法：是將待求解的問(wèn)題分解為假設(shè)干個(gè)子問(wèn)題(階段),按順序求解子階段,前一子問(wèn)題白夕解,.方后一了vn題的求j提供wn用的信息. 在求解任一子問(wèn) m(n, jj題時(shí),列出各種前能的局部解,頓過(guò)頓保勺那些w能到達(dá)最優(yōu)白局部解, 丟 棄其他局部解.依次解決各子問(wèn)題,最后一個(gè)子問(wèn)題就是初始問(wèn)題的解.mq由/聲態(tài)規(guī)maxmfe多或43刖(i可題和j特?zé)醝) M少重復(fù)j十算"對(duì)每一個(gè)子問(wèn)題只解一次,將其不同網(wǎng)"不加13保存在一個(gè)二維數(shù)

3、組0. j wi設(shè)所給0-1背包問(wèn)題的子問(wèn)題的最優(yōu)值為m(i , j),即m(i , j)是背包容量為j ,可選擇物品為i , i+1 ,n時(shí)0-1背包問(wèn)題的最優(yōu)值.由0-1背包問(wèn)題 的最優(yōu)子結(jié)構(gòu)性質(zhì),可以建立計(jì)算 m(i , j)的遞歸式如下.回溯法：在問(wèn)題的解空間樹(shù)中,按深度優(yōu)先策略,從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù) 算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí), 先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解.如果肯定 不包含,那么跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索,逐層向其祖先結(jié)點(diǎn)回溯；否那么,進(jìn) 入該子樹(shù),繼續(xù)按深度優(yōu)先策略搜索.(2)背包問(wèn)題貪心算法：首先計(jì)算每種物品單位重量的價(jià)值 Vi/Wi ,然后,依貪心選擇策略, 將盡可

4、能多的單位重量?jī)r(jià)值最高的物品裝入背包.假設(shè)將這種物品全部裝入背包后,背包內(nèi)的物品總重量未超過(guò) C,那么選擇單位重量?jī)r(jià)值次高的物品并盡可能多 地裝入背包.依此策略一直地進(jìn)行下去,直到背包裝滿為止.三.測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1 .正常測(cè)試數(shù)據(jù)(3組)及運(yùn)行結(jié)果0-1背包問(wèn)題：動(dòng)態(tài)規(guī)劃法：'JzXCeb ug'ULrroA.ndC neXna psackt法輸入背包總等置：lu請(qǐng)輪A物船用裊二5請(qǐng)輸入第1個(gè)沖幾的麗曲叫價(jià)值：2 R有輸入策個(gè)物品的?造F.儕值13 3土里入第材一物品的里整及儕值：8 5片輸入第4個(gè)物品的更研及價(jià)值：9 4擊裁A第個(gè)物品粕蟲(chóng)魚(yú)反價(jià)值:4 gResj Iu.

5、tNumber： 1. Mmb*rr 2. Number： 5, 卜,es arw Ley to cont i *j(j回溯法: rJDs bugZeraAndOnE <na2 ssckl 回恒 L eke"由輸入背包號(hào)大藥堂：10請(qǐng)飾入可選杓品數(shù)疝：5痂入第1號(hào)物品的事量和精值;2 6輸入第2號(hào)粉品的莫三加府情：2 3輸入第d號(hào)物品的串晝和恂俗:I： 5軸入第4號(hào)粉J的奧量和儕值:5 4仲入灣54忱品的重量,和價(jià)值:4 6排序后的物品內(nèi)容如下：青包最大能裝的直較為：1.,5價(jià)給6.00價(jià)值：3.00價(jià)咱：6.00價(jià)哨：5.00於情：九叩第1號(hào)您品望:2.00,1 革?朝品篁：

6、工況 第3號(hào)物品至：4二0 第4號(hào)物品重：6X0/ 第5號(hào)曾品篁;5,削,1 'J;E>dc ug'_ZroAndOn?Knapssc k目釐二G 5縮入第4號(hào)蛻品的愛(ài)fi:卻1介源；p 4哈占第&號(hào)拗品的省量和帕田:18棺序總后物品內(nèi)容B下；背包屋大能裝的更靠弁：m.00o .u D o n oo OOO IK- d + 6 3 6 5 4曙】號(hào)坳品重：2.00,®： 短號(hào)物品量;2M加值: 需3號(hào)物品至：4.口口,價(jià)也: 庠4號(hào)喇品生：機(jī)00,行傳: 品5號(hào)的品巫；5.1口,價(jià)使:所有押品包至量西：17.川,總價(jià)值沏：刈0聞相U下物品裝入背包,便背包

7、建的物品仍倒導(dǎo)大： 帚1號(hào)物品,生量：2X0,愉值:B.OO腳號(hào)陶品,里前:4口,初值;6.01,包中利品的大翥量為：6 口最最大價(jià)方為：15.00Press -any key 1 cent nue背包問(wèn)題:貪心算法:I 1回 Z口靖徜入苜笆總?cè)萁欢?1 'I,犒人物品個(gè)女工山諭入第1個(gè)物品的叟直及價(jià)但:2 6適泊又第2個(gè)物品的重量及仲置!b 3請(qǐng)輸入羯甘個(gè)物品的毒量盤價(jià)值:R h請(qǐng)輸A第4個(gè)物品的穿營(yíng)及抑值R -I請(qǐng)篩人竄?b物拈的中后質(zhì)價(jià)值; K ERmgjIt;rluirfaer： 1 Weishl ： ?.00Njfflber： 2, Wei時(shí)M 2.10-Nuintoer：

8、5,照 15Hl 4.00 卜kinbar： 3,也 ifiH： 2. U pjiriValue- 16.07Pr*E£ an/ *.«y to zvd i rut四.調(diào)試情況,設(shè)計(jì)技巧及體會(huì)本次的實(shí)驗(yàn)大體理解和掌握 0-1背包動(dòng)態(tài)規(guī)劃算法、回溯算法和背包貪 心算法的問(wèn)題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)、算法復(fù)雜性分析、他們的區(qū)別 及聯(lián)系.通過(guò)本次上機(jī)實(shí)驗(yàn),我對(duì) 0-1背包動(dòng)態(tài)規(guī)劃算法、回溯算法和背包貪心算法)有了更為深刻的了解,利用動(dòng)態(tài)規(guī)劃算法、回溯算法和貪心可以將問(wèn)題簡(jiǎn)化,這有助于我們?cè)趯?shí)際問(wèn)題中解決一些復(fù)雜性較大的問(wèn)題,提升程序的運(yùn)行效率.但要注意他們的區(qū)別與不同的應(yīng)用場(chǎng)

9、景.五.源代碼1) 0-1背包：動(dòng)態(tài)規(guī)劃法：#include <>#define MAX 20void Knapsack(int *value, int *weight, int column, 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;

10、int Max(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; i+)if(middleicolumn = middlei + 1column)xi = 0;else (xi = 1;column -= weighti; )xlength = (middlelengthcolumn 1 : 0); )void Knapsack(int *value, in

11、t *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 = weightlength; j <= column; j+) middlelengthj = valuelength;for(i = length - 1; i > 1; i-)(jMax = Min(weighti - 1, column);for(j = 0; j <

12、= jMax; j+)middleij = middlei + 1j;for(j = weighti; j <= column; j+)middleij = Max(middlei + 1j, middlei + 1j - weighti + valuei);)middle1column = middle2column;if(column >= weight1) middle1column = Max(middle1column, middle2column - weight1 + value1);void main(void)int i, length, column, coun

13、t = 0, weightMAX, valueMAX, xMAX = 0, middleMAXMAX = 0;printf("請(qǐng)輸入背包總?cè)萘浚簄");scanf("%d", &column);printf("請(qǐng)輸入物品個(gè)數(shù)：n");scanf("%d", &length);if(length < 1)printf("輸入錯(cuò)誤！ ！ n");return;for(i = 1; i <= length; i+)printf("請(qǐng)輸入第d個(gè)物品的重量及價(jià)值：n&

14、quot;, i);scanf("%d %d", weight + i, value + i);Knapsack(value, weight, column, length, middle);TraceBack(middle, weight, column, length, x);printf("Result:n");for(i = 1; i <= length; i+)if(xi)printf("Number: %d, ", i);printf("n");)回溯法：#include <>#inc

15、lude <>#include <>typedef struct goodsint num;double *value;double *weight;int *location;double column;double currentWeight;double currentValue;double bestValue;GOODS;void Knapsack(GOODS *goods, int i);double Bound(GOODS *goods, int i);void SwapDouble(double *m, double *n);void SwapInt(i

16、nt *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 <= goods -> num; i+)tempi = goods -> valuei / goods -> weighti;for(i = 1; i < goods -> num; i+)for(j = i + 1; j <= goods -> nu

17、m; j+)if(tempi < tempj)SwapDouble(&tempi, &tempj);SwapDouble(&goods -> weighti, &goods -> weightj);SwapDouble(&goods -> valuei, &goods -> valuej);SwapInt(&goods -> locationi, &goods -> locationj);void SwapInt(int *m, int *n)int temp;temp = *m;* m

18、= *n;* n = temp;void SwapDouble(double *m, double *n)(double temp;temp = *m;* m = *n;*n = temp;)double Bound(GOODS *goods, int i)(double leftWeight = goods -> column - goods -> currentWeight;double bound = goods -> currentValue;while(i <= goods -> num && goods -> weighti &l

19、t;= leftWeight)(leftWeight -= goods -> weighti;bound += goods -> valuei;i+;)if(i <= goods -> num)bound += goods -> valuei * leftWeight / goods -> weighti;return bound;void Knapsack(GOODS *goods, int i) (if(i > goods -> num)(goods -> bestValue = goods -> currentValue;ret

20、urn;if(goods -> currentWeight + goods -> weighti <= goods -> column)goods -> locationi = 1;goods -> currentWeight += goods -> weighti;goods -> currentValue += goods -> valuei;Knapsack(goods, i + 1);goods -> currentWeight -= goods -> weighti;goods -> currentValue -

21、= 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 = (GOODS *)malloc(sizeof(GOODS)printf("內(nèi)存

22、分配失敗n");exit(0);goods -> currentValue = goods -> currentWeight = goods -> bestValue=;printf(" 請(qǐng)輸入背包最大重量：n");scanf("%lf", &goods -> column);printf("請(qǐng)輸入可選物品數(shù)量：n");scanf("%d", &goods -> num);if(!(goods -> value = (double *)malloc(si

23、zeof(double) * (goods -> num+ 1)printf("內(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

24、(i = 1; i <= goods -> num; i+)goods -> locationi = 0;for(i = 1; i <= goods -> num; i+)printf("輸入第d號(hào)物品的重量和價(jià)值：n", i);scanf("%lf %lf", &goods -> weighti, &goods -> valuei);totalValue += goods -> valuei;totalWeight += goods -> weighti;)Sort(goods);p

25、rintf("n排序后的物品內(nèi)容如下：n");printf("n背包最大能裝的重量為：%.2lfnn",goods -> column);for(i = 1; i <= goods -> num; i+)goods ->printf(" 第 d 號(hào)物 品重：%.2lf,價(jià)值:%.2lfn", i, weighti, goods -> valuei);printf("n所有物品總重量為：%.2lf,總價(jià)值為：%.2lfnn", totalWeight,totalValue);Knapsa

26、ck(goods, 1);printf("n可將以下物品裝入背包,使背包裝的物品價(jià)值最大：n");for (i = 1; i <= goods -> num; i+)if(goods -> locationi)printf("第d#物品,重量：.2lf, 價(jià)值：.2lfn", i, goods ->weighti, goods -> valuei);sumWeight += goods -> weighti;printf("n背包中物品最大重量為：.2lf,最大價(jià)值為：%.2lfn",sumWeig

27、ht, goods -> bestValue);2)背包問(wèn)題：貪心算法：#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;temp = *m;*m = *n;*n = temp;

28、)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 = 0; i < length; i+)(mid