资源描述：
《0-1背包(动态规划、回溯)和背包(贪心)实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、西安郵電學院算法设计与分析课内试豔报告题目:背包（动态规划、回溯）和背包（贪心）院系名称：计算机学院专业名称：软件工程专业班级：0903班学生姓名：輕学号（8位）：04095091（23）指导教师：»时间：2011年12月一.设计目的通过上机实验：深刻理解和掌握0・1背包(动态规划算法、回溯算法)和背包(贪心算法)的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。二.设计内容1问题的描述(1)0-1背包问题给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？(2)背包问题与0・
2、1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，lv=iv=n。2算法设计思想(1)0-1背包问题动态规划法：是将待求解的问题分解为若干个子问题(阶段)，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列岀各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。设所给0-1背包问题的子问题的
3、最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i,i+1,…，n吋0・1背包问题的最优值。由0・1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下。m(i,7)=回溯法：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。(2)背包问题贪心算法：首先计算每种物品单位重量的价值Vi/Wi,然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全
4、部装入背包后，背包内的物晶总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。一.测试数据及运行结果1.正常测试数据(3组)及运行结果0-1背包问题：动态规划法：回溯法:**J:DebugZeroAndOneKnap$ack（回溯）・exe"请输入背包最大重量：10请输入可选物品O：5输入第1号物品的重量和价值:26输入第2号物品的重量和价值:23输入第3号物品的重量和价值:65输入第4号物品的重量和价值:54输入第5号物品的重量和价值:46排序后的物品内容如下:背包最大能装的重量为：10.00第1号物品重:2.00/
5、第2号物品重:2.00/第3号物品重：4.00/第4号物品重：6.00/第5号物品重:5.00/ooooOooooO•••654值值值值值介介介介介・•J:DebugZeroAndOneKnapsack（回溯）・exe”65输入第4号物品的重量和价值：54输入第5号物品的重量和价值：46排序后的物品内容如下：背包最大能装的重量为：10.00第1号物品重：2.00,1第2号物品重：2.00,1第3号物品重：4.00,1第4号物品重：6.00,1笫5号物品重：5.00,1介值:介值:介值:介值:介值:6.003.006.005.004.00所有物品总垂量为：19.00,总价值为
6、：24.00可将以下物品装入背包,使背包装的物品价值最大:第1号物品，畫量：2.00,价值：6.00第3号物品，重量：4.00,价值：6.00背包中物品最大重量为：6.00,最大价值为：15.00Pressanykeytoconiinue背包问题:贪心算法:■J'Debug'KnapsacIc（贪心）・exe*10请输入物品个数：5请输入第1个物品的重园及价值:26请输入第2个物品的重量及价值:23请输入第3个物品的重量及价值:65请输入第4个物品的重量及价值:54请输入第5个物品的更量及价值:46Weight:2.00Weight:2.00Weight:4.00Weight:
7、2.00ResuIt:1,2,5,3,Number：bkjmber：Number：bkimber：SumValue：16.67Pressanykeytocontinue一.调试情况，设计技巧及体会木次的实验大体理解和掌握0・1背包（动态规划算法、回溯算法）和背包（贪心算法）的问题描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。通过本次上机实验，我对0・1背包（动态规划算法、回溯算法）和背包（贪心算法）有了更为深刻的了解，利用动态规划算法、回溯算法和贪心可以将问题简化,这有助于
