西安院
算法设计与分析课内试验报告
题目：01背包动态规划、回溯和背包贪心
院系名称：
计算机学院
专业名称：
软件工程专业
班级：学生姓名：
0903班张桥
学号（8位）：指导教师：
0409509123陈琳
时间：
2011年12月
f一设计目的通过上机实验：深刻理解和掌握01背包动态规划算法、回溯算法和背包贪心算法的问题
描述、算法设计思想、程序设计、算法复杂性分析、他们的区别及联系。二设计内容1问题的描述
101背包问题给定
种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？2背包问题与01背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1i
。2算法设计思想101背包问题动态规划法：是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。设所给01背包问题的子问题的最优值为mi，j，即mi，j是背包容量为j，可选择物品为i，i1，…，
时01背包问题的最优值。由01背包问题的最优子结构性质，可以建立计算mi，j的递归式如下。
m
jv0

jw
0jw

mi
j

maxmi
1jmi1mi1j
j

wi

vi
jwi0jwi
回溯法：在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
f2背包问题贪心算法：首先计算每种物品单位重量的价值ViWi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。三．测试数据及运行结果1．正常测试数据（3组）及运行结果01背包问题：
动态规划法：
回溯法：
f背包问题：贪心算法：
四．调试情况r