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

西安郵電學院 目：0-1背包(动态规划、回溯)和背包(贪心) 院系名称： 计算机学院 专业名称： 软件工程专业 班 级： 0903班 学生姓名： 张桥 学号（8位）： 23) 指导教师： 陈琳 时间： 2011年12月一. 设计目的 通过上机实验： 深刻理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。 二. 设计内容 1问题的描述 0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？ (2)背包问题与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1=i=n。 2算法设计思想 (1)0-1背包问题 动态规划法：是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。 设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。 回溯法：在问题的解空间树中，按深度优先策略，从根结点出发有哪些信誉好的足球投注网站解空间树。算法有哪些信誉好的足球投注网站至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的有哪些信誉好的足球投注网站，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略有哪些信誉好的足球投注网站。 背包问题 贪心算法：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 三．测试数据及运行结果 正常测试数据（3组）及运行结果 0-1背包问题： 动态规划法： 回溯法： 背包问题： 贪心算法： 四．调试情况，设计技巧及体会 本次的实验大体理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。 通过本次上机实验，我对0-1背包(动态规划算法、回溯算法)和背包(贪心算法)有了更为深刻的了解，利用动态规划算法、回溯算法和贪心可以将问题简化，这有助于我们在实际问题中解决一些复杂性较大的问题，提高程序的运行效率。但要注意他们的区别与不同的应用场景。 五. 源代码 1）0-1背包： 动态规划法： #include stdio.h #define MAX 20 void 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; } 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(middle[i][column] == middle[i + 1][column]) x[i] = 0; else { x[i] = 1; column -= weight[i]; } x[length] = (middle[length][column] ? 1 : 0); } void Knapsack(int *value, int *weight, int column, int length,