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