0-1背包(动态规划、回溯)和背包(贪心)实验报告

1、西安垂院算法设计与分析课内试验报告题 目：0-1背包（动态规划、回溯）和背包（贪心）院系名称：计算机学院专业名称：软件工程专业班 级： 0903 班学生姓名：1W学号（8 位）:04095091（23）指导教师：W时间：2011年12月一 . 设计目的通过上机实验：深刻理解和掌握0-1 背包 （ 动态规划算法、 回溯算法 ） 和背包 （ 贪心算法 ） 的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。二 . 设计内容1 问题的描述（1）0-1 背包问题给定 n 种物品和一背包。 物品 i 的重量是 wi ， 其价值为 vi ， 背包的容量为 c问应如何选择装入背包中的物品，

2、使得装入背包中物品的总价值最大（2） 背包问题与0-1 背包问题类似，所不同的是在选择物品 i 装入背包时，可以选择物品 i 的一部分，而不一定要全部装入背包， 1<=i<=n 。2 算法设计思想（1）0-1 背包问题 动态规划法：是将待求解的问题分解为若干个子问题（阶段） ，按顺序求解子阶段， 前一子问题的解， 为后一子问题的求解提供了有用的信息。 vn jwn在求解任一子问m（n, j）题时， 列出各种可能的局部解，0通过决策保留那些有可能达到最优的局部解，0 j w丢 弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。m（i由jf态规maxmfe多或j,刖可题1

3、, j特型i ） M少重复j十算wi对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。 m（i 1,j）0 j wi设所给 0-1 背包问题的子问题的最优值为 m（i ， j） ，即 m（i ， j） 是背包容量为j ,可选择物品为i , i+1 ,，n时0-1背包问题的最优值。由0-1背包问题m（i ， j） 的递归式如下。回溯法：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树 算法搜索至解空间树的任意一点时， 先判断该结点是否包含问题的解。如果肯定 不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进 入该子树，继续按深度优先策略搜索。(2

4、)背包问题贪心算法：首先计算每种物品单位重量的价值 Vi/Wi ,然后，依贪心选择策略, 将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过 C,则选择单位重量价值次高的物品并尽可能多 地装入背包。依此策略一直地进行下去，直到背包装满为止。三.测试数据及运行结果1 .正常测试数据(3组)及运行结果0-1背包问题：动态规划法：'JzXCeb ug'ULrroA.ndC neXna psackt法输入背包总等置：lu请轮A物船用袅二5请输入第1个冲几的丽曲叫价值：2 R有输入策个物品的造F.侪值13 3土里入第材一物品的里整及侪值：8

5、5片输入第4个物品的更研及价值：9 4击裁A第个物品粕虫鱼反价值:4 gResj Iu. tNumber： 1. Mmb*rr 2. Number： 5, 卜，es arw Ley to cont i *j(j回溯法: rJDs bugZeraAndOnE <na2 ssckl 回恒 L eke"由输入背包号大药堂：10请饰入可选杓品数疝：5痂入第1号物品的事量和精值;2 6输入第2号粉品的莫三加府情：2 3输入第d号物品的串昼和恂俗:I： 5轴入第4号粉J的奥量和侪值:5 4仲入湾54忱品的重量,和价值:4 6排序后的物品内容如下：青包最大能装的直较为：1。,5价给6.00价

6、值：3.00价咱：6.00价哨：5.00於情：九叩第1号您品望:2.00,1 革?”朝品篁：工况 第3号物品至：4二0 第4号物品重：6X0/ 第5号曾品篁;5,削,1 'J;E>dc ug'_ZroAndOn?Knapssc k（目釐二G 5缩入第4号蜕品的爱fi:却1介源；p 4哈占第&号拗品的省量和帕田:18棺序总后物品内容B下；背包屋大能装的更靠弁：m.00o .u D o n oo OOO IK- d + 6 3 6 5 4曙】号坳品重：2.00,（®： 短号物品量;2M加值: 需3号物品至：4.口口，价也: 庠4号喇品生：机00,行传: 品5

7、号的品巫；5.1口,价使:所有押品包至量西：17.川，总价值沏：刈（0闻相U下物品装入背包,便背包建的物品仍倒导大： 帚1号物品,生量：2X0,愉值:B.OO脚号陶品,里前:4口,初值;6.01，包中利品的大翥量为：6 口最最大价方为：15.00Press -any key 1 cent nue背包问题:贪心算法:I 1回 Z口靖徜入苜笆总容交二11 'I，犒人物品个女工山谕入第1个物品的叟直及价但:2 6适泊又第2个物品的重量及仲置!b 3请输入羯甘个物品的毒量盘价值:R h请输A第4个物品的穿营及抑值R -I请筛人窜b物拈的中后质价值; K ERmgjIt;rluirfaer： 1

8、 Weishl ： ?.00Njfflber： 2, Wei时M 2.10-Nuintoer： 5,照 15Hl 4.00 卜kinbar： 3,也 ifiH： 2. U pjiriValue- 16.07Pr*E£ an/ *.«y to zvd i rut四.调试情况，设计技巧及体会本次的实验大体理解和掌握 0-1背包（动态规划算法、回溯算法）和背包（贪 心算法）的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别 及联系。通过本次上机实验，我对 0-1背包（动态规划算法、回溯算法）和背包（贪心算法 ) 有了更为深刻的了解，利用动态规划算法、回溯算法和贪心可以

9、将问题简化， 这有助于我们在实际问题中解决一些复杂性较大的问题， 提高程序的运行效率。但要注意他们的区别与不同的应用场景。五 . 源代码1) 0-1 背包：动态规划法：#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

10、Min(int x, int y);int Min(int x, int y)return x <= y x : y;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;elsexi = 1;column -= weighti;xlength =

11、 (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 = weightlength; j <= column; j+) middlelengthj = valuelength;for(i = length - 1; i > 1

12、; i-)jMax = Min(weighti - 1, column);for(j = 0; j <= 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+

13、 value1);void main(void)int i, length, column, count = 0, weightMAX, valueMAX, xMAX = 0, middleMAXMAX = 0;printf(" 请输入背包总容量： n");scanf("%d", &column);printf(" 请输入物品个数： n");scanf("%d", &length);if(length < 1)printf(" 输入错误！ ！ ！ n");return;fo

14、r(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);printf("Result:n");for(i = 1; i <= length; i+)printf("Number: %d, ",

15、 i);printf("n");回溯法：#include <>#include <>#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);v

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

17、> num; i+)for(j = i + 1; j <= goods -> num; j+)if(tempi < tempj)SwapDouble(&tempi, &tempj);SwapDouble(&goods -> weighti, &goods -> weightj);SwapDouble(&goods -> valuei, &goods -> valuej);SwapInt(&goods -> locationi, &goods -> locationj);v

18、oid SwapInt(int *m, int *n)int temp;temp = *m;* m = *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 <= go

19、ods -> num && goods -> weighti <= 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 ->

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

21、s -> 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

22、OODS *)malloc(sizeof(GOODS)printf(" 内存分配失败n");exit(0);goods -> currentValue = goods -> currentWeight = goods -> bestValue= ;printf("请输入背包最大重量:n");scanf("%lf", &goods -> column);printf("请输入可选物品数量:n");scanf("%d", &goods -> num);i

23、f(!(goods -> value = (double *)malloc(sizeof(double) * (goods -> num+ 1)printf(" 内存分配失败n");exit(0);if(!(goods -> weight = (double *)malloc(sizeof(double) * (goods ->num + 1)printf（" 内存分配失败n"）;exit(0);if(!(goods -> location = (int *)malloc(sizeof(int) * (goods ->

24、 num+ 1)printf(" 内存分配失败n");exit(0);for(i = 1; i <= goods -> num; i+)goods -> locationi = 0;for(i = 1; i <= goods -> num; i+)printf(" 输入第d号物品的重量和价值：n", i);scanf("%lf %lf", &goods -> weighti, &goods -> valuei);totalValue += goods -> valuei;

25、totalWeight += goods -> weighti;Sort(goods);printf("n 排序后的物品内容如下： n");printf("n 背包最大能装的重量为 : %.2lfnn",goods -> column);goods ->for(i = 1; i <= goods -> num; i+)printf(" 第 %d 号 物 品 重 : %.2lf, 价 值 : %.2lfn", i, weighti, goods -> valuei);printf("n 所有

26、物品总重量为： %.2lf ， 总价值为 : %.2lfnn", totalWeight,totalValue);Knapsack(goods, 1);printf("n 可将以下物品装入背包 , 使背包装的物品价值最大:n");for (i = 1; i <= goods -> num; i+)if(goods -> locationi) printf("第打物品，重量：.2lf, 价值：.2lfn", i, goods ->weighti, goods -> valuei);sumWeight += goods

27、 -> weighti;printf("n 背包中物品最大重量为 : %.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, do

28、uble *n);void Swap(double *m, double *n) double temp;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 = 0; i < leng