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

1、西安郵電學院算法设计与分析课内试验报告题目：0-1 背包( 动态规划、回溯 ) 和背包 ( 贪心 )院系名称：计算机学院专业名称：软件工程专业班级： 0903班学生姓名：张桥学号（ 8 位） ： 04095091(23)指导教师：陈琳时间：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 背包问题动态规划法：是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解， 为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解， 通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算， 对每一个子问题只解一次，将其

3、不同阶段的不同状态保存在一个二维数组中。设所给 0-1 背包问题的子问题的最优值为m(i ，j) ，即 m(i ，j) 是背包容量为 j ，可选择物品为 i ，i+1 ，n 时 0-1 背包问题的最优值。由0-1 背包问题的最优子结构性质，可以建立计算m(i ，j) 的递归式如下。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),(回溯法：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回

4、溯；否则，进入该子树，继续按深度优先策略搜索。(2) 背包问题贪心算法：首先计算每种物品单位重量的价值vi/wi ，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。三测试数据及运行结果1正常测试数据（ 3 组）及运行结果0-1 背包问题：动态规划法：回溯法：背包问题：贪心算法：四调试情况，设计技巧及体会本次的实验大体理解和掌握0-1 背包( 动态规划算法、回溯算法 ) 和背包 (贪心算法 ) 的问题描述、算法设计思想、程序设计、算

5、法复杂性分析、他们的区别及联系。通过本次上机实验，我对0-1 背包(动态规划算法、回溯算法)和背包 ( 贪心算法) 有了更为深刻的了解，利用动态规划算法、回溯算法和贪心可以将问题简化，这有助于我们在实际问题中解决一些复杂性较大的问题，提高程序的运行效率。但要注意他们的区别与不同的应用场景。五. 源代码1）0-1 背包：动态规划法：#include #define max 20void knapsack(int *value, int *weight, int column, int length, int (*middle)max);void traceback(int (*middle)ma

6、x, 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; i+)if(middleicolumn = middlei + 1column)xi = 0;elsexi = 1;column

7、 -= 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 = weightlength; j 1; i-)jmax = min(weighti - 1, column);for(j = 0; j = jmax;

8、 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;printf(请输入背包总容量：n);scanf(%d, &column);printf(请输入物品个数：n);scanf(%d, &le

9、ngth);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);printf(result:n);for(i = 1; i = length; i+)if(xi)printf(number: %d, , i);

10、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);void swapdouble(double *m, double *n);

11、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;for(i = 1; i num; i+)for(j = i + 1; j num; j+)if(tempi weighti, &goods - weightj);swapdo

12、uble(&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;temp = *m;*m = *n;*n = temp;double bound(goods *goods, int i)double leftweight = go

13、ods - 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 bound;void knapsack(goods *goods, int i)if(i goods - num)goods - bestvalue = goods - cu

14、rrentvalue;return;if(goods - currentweight + goods - weighti column)goods - locationi = 1;goods - currentweight += goods - weighti;goods - currentvalue += goods - valuei;knapsack(goods, i + 1);goods - currentweight -= goods - weighti;goods - currentvalue -= goods - valuei;if(bound(goods, i + 1) good

15、s - 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);exit(0); goods - currentvalue = goods - currentweight = goo

16、ds - bestvalue = ;printf(请输入背包最大重量 :n);scanf(%lf, &goods - column);printf(请输入可选物品数量 :n); scanf(%d, &goods - num);if(!(goods - value = (double *)malloc(sizeof(double) * (goods - num + 1)printf(内存分配失败 n);exit(0); if(!(goods - weight = (double *)malloc(sizeof(double) * (goods - num + 1)printf(内

17、存分配失败 n);exit(0); if(!(goods - location = (int *)malloc(sizeof(int) * (goods - num + 1)printf(内存分配失败 n);exit(0); for(i = 1; i num; i+)goods - locationi = 0;for(i = 1; i num; i+)printf(输入第 %d号物品的重量和价值 :n, i);scanf(%lf %lf, &goods - weighti, &goods - valuei);totalvalue += goods - valuei;totalw

18、eight += goods - weighti;sort(goods);printf(n排序后的物品内容如下：n);printf(n背包最大能装的重量为 : %.2lfnn,goods - column);for(i = 1; i num; i+)printf(第 %d 号 物 品 重 : %.2lf,价 值 : %.2lfn, i, goods - weighti, goods - valuei);printf(n所有物品总重量为：%.2lf ， 总价值为 : %.2lfnn, totalweight, totalvalue);knapsack(goods, 1);printf(n可将以下

19、物品装入背包 , 使背包装的物品价值最大:n);for (i = 1; i num; i+)if(goods - locationi)printf(第%d号物品 , 重量: %.2lf, 价值: %.2lfn, i, goods - weighti, goods - valuei);sumweight += goods - weighti; printf(n背包中物品最大重量为: %.2lf, 最大价值为: %.2lfn, sumweight, goods - bestvalue);2）背包问题：贪心算法：#include #define max 10void knapsack(int *va

20、lue, 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;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