1、 江 西 财 经 大 学课程设计报告课程：算法设计与分析班级： 08 计算机 2 班学号： 0082900 姓名： 叶小玉 完成时间：2010-12-310/1 背包问题一、 设计目的1）掌握贪心法的原理及使用环境。2）掌握动态规划法的原理及使用环境；3）掌握分枝限界法的原理及使用环境；4）分析三种算法的特点。二、 设计内容1. 任务描述1）0/1 背包问题简介已知一个载重为 M 的背包和 n 件物品，第 i 件物品的重量为 Wi，如果将第i 件物品全部装入背包，将有收益 Pi（Wi0，Pi0，0i0，Wi0 ,Vi0, ,要求找ni1一个 n 元 0-1 向量（X1,X2,.,Xn） ，Xi
2、=0 或 1， ，使得i,WiX1niM而且 到最大。n1iP数学模型为：max n1iX,1niMXi=0 或 1， ni约束条件三求解 0/1 背包问题3.1 利用贪心法求解 0/1 背包问题3.1.1 算法思想贪心算法采用逐步构造最优解的方法，在每个阶段，都在一定的标准下做出 一个看上 去最优的决策，0/1 背包选择单位效益最高贪心准则，即从剩余物 品中选择可装入包的 Pi/Wi 值最大的物品。3.1.2 主要模块说明void bagloading(int x,float p,float w,float M,int n,int hao) float t,k,pwnum;int i,j,m
3、,kk,q;for(i=0;i0) kk=0;for(j=0;j1;i-) /递归部分 jmax=min(weii-1,M); for(int j=0;j=wei1) m1M=max(m1M,m2M-wei1+val1); cout“价值和为：“m1Mendl; 3.2.3 算法分析动态规划求解 0/1 背包问题的复杂度为 .动态规划主要是求 ），（ n2Mmi解最优决策序列。当最优决策序列中包含最优决策子序列时候，可建立动态 规划递归方程，可以帮助高效率的解决问题。3.2.4 测试结果与分析结果截图：动态规划算法处理 0/1 背包问题可以求的最优解。但是因为需要找最优子决 策因此时间相对来说
4、较慢。3.3 利用分枝限界法求解 0/1 背包问题3.3.1 算法思想0/1 背包问题的分支限界发可以使用最大收益算法定界函数来计算活结点 的收益上限 up，使得以活结点为根的子树中的任一节点的收益值都不可能 超过 up，活结点的最大堆使用 up 作为关键值域。在子集树中执行最大收益 分支定界搜索的函数首先初始化活结点的最大堆，并使用一个数组 best 来 动态规划思想-寻找最优决策记录最优解。由于需要不断的利用收益密度来排序，物品的索引值会随之变 化，因此必须将函数所产生的结果映射到初始是的物品索引。函数中的循环 首先检验 E 节点做孩子的可行性，如果可行，将它加入子集树和活结点队 列；仅当
5、节点有孩子的定界值指明可能找到一个最优解是才将有孩子加入子 集树和队列中。3.3.2 主要模块说明数据结构：struct node/结点表结点数据结构node *parent,/父结点指针*next; /后继结点指针int level,/结点的层bag,/节点的解cw,/当前背包装载量 cp;/当前背包价值 float ub; /结点的上界值;class Knapprivate:struct node *front, *bestp,*first; /解结点、根结点int *p,*w,n,c,*M;/背包价值、重量、物品数、背包容量、记录大小顺序关系long lbestp;/背包容量最优解 pu
6、blic:void Sort();Knap(int *pp,int *ww,int cc,int nn);Knap();float Bound(int i,int cw,int cp);/计算上界限node *nnoder(node *pa,int ba,float uub);/生成一个结点 ba=1 生成左节点 ba=0 生成右节点void addnode(node *nod);/将结点添加到队列中void deletenode(node *nod);/将结点队列中删除struct node *nextnode(); /取下一个void display(); /输出结果void solveb
7、ag(); /背包问题求解;3.3.3 算法分析分支限界法处理 0/1 问题的时间复杂度为 ，分支限界算法将所有的）（ n2结 果形成一棵树，但是在生成树的过程中会剪断一些不符合要求的枝来简化算 法的计算。分支限界法需要算出一般背包问题，将一般背包问题作为一个限 界值，根据自身的约束，实现剪枝的目的.分支限界法容易求得最优解，但是 时间效率并不高。分支限界法可以求出 0/1 背包的最优解。但是因为它是以 树为基础的算法，因此它的空间开销也要大。3.3.4 测试结果与分析结果截图：分支限界法可以求的 0/1 背包的最优解，速度也较快，但是在构造树时候花 费了较多的空间。当需要空间不大时候，需慎用
8、。四. 总结与讨论通过对以上 0/1 背包问题的求解分析，可以了解到各种算法设计 方法有各自不同的特点，针对不同的问题领域，他们有不同的效 率。通过对 0/1 背包问题求解，对贪心法，动态规划法和分支限 界法的原理用了进一步的了解，另外他们各自的使用条件，算法 的优缺点是我们选择算法要考虑的。总结上叙分析他们各自的优 缺点可以得出如下比较。1.贪心法：处理问题的速度快，思想简单。使用该方法的必要条 件是寻找好的贪心法则。不足之处在于很多时候它只能求的似优 解，却不能求的最优解 2.动态规划法：可以求解最优解，重点在于徐兆最优决策序列， 但是速度较慢。3.分支限界法：可以求解最优解，重点在于寻找限界值。易求最优解，但是空间花费较高，效率不是很高。选择哪一种算法，不仅要根据问题本身还需要考虑到其他因素， 例如时间复杂度，空间复杂度，易求解等等因素。
