资源描述：
《背包（动态规划回溯）和背包（贪心）实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、西安郵電學院算法设计与分析课内试验报告题目：0-1背包(动态规划、回溯)和背包(贪心)院系名称：计算机学院专业名称：软件工程专业班级：0903班学生姓名：张桥学号（8位）：(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)的递归式如下。回溯法：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。(1)背包问题贪心算法：首先计算每种物品
4、单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。三．测试数据及运行结果1．正常测试数据（3组）及运行结果0-1背包问题：动态规划法：回溯法：背包问题：贪心算法：四．调试情况，设计技巧及体会本次的实验大体理解和掌握0-1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。通过本次上机实
5、验，我对0-1背包(动态规划算法、回溯算法)和背包(贪心算法)有了更为深刻的了解，利用动态规划算法、回溯算法和贪心可以将问题简化，这有助于我们在实际问题中解决一些复杂性较大的问题，提高程序的运行效率。但要注意他们的区别与不同的应用场景。五.源代码1）0-1背包：动态规划法：#include#defineMAX20voidKnapsack(int*value,int*weight,intcolumn,intlength,int(*middle)[MAX]);voidTraceBack(int(*middle)[MAX],
6、int*weight,intcolumn,intlength,int*x);intMax(intx,inty);intMin(intx,inty);intMin(intx,inty){returnx<=y?x:y;}intMax(intx,inty){returnx>=y?x:y;}voidTraceBack(int(*middle)[MAX],int*weight,intcolumn,intlength,int*x){inti;for(i=1;i7、[column])x[i]=0;else{x[i]=1;column-=weight[i];}x[length]=(middle[length][column]?1:0);}voidKnapsack(int*value,int*weight,intcolumn,intlength,int(*middle)[MAX]){inti,j,jMax=Min(weight[length]-1,column);for(j=0;j<=jMax;j++)middle[length][j]=0;for(j=weight[length];j<=column
8、;j++)middle[length][j]=value[length];for(i=length-1;i>1;i--){jMax=Min(weight[i]-1,column);for(j=0;j<=jM
