背包问题实验报告(共3页).doc
精选优质文档-倾情为你奉上0-1背包问题实验报告一问题描述1. 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。2. 在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。二问题规模1物品数目：n=50，2背包容量：c=1000，3每个物品重量分别为：220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1,14 每个物品价值分别为：80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1三实验方法本次实验将分别通过动态规划法，贪心算法，回溯法及分支界限法四种方法解决0-1背包问题。四算法分析.动态规划法（1）.对动态规划的0-1背包问题，在给定c>0, >0，>0，1<=i<=n，要求找出一个n元0-1向量（x1,x2,xn）， 0，1,1in；使得，而且。同时可得出其递推关系，设最优值mi,j是背包容量为j，可选物品i,i+1,n时0-1背包问题的最优值。于是可建立计算m(I,j)的递归式：mi,j在j>=,为maxm(i+1,j),m(i+1,j-)+,在0<=j<时，m(i+1,j);mn,j在j>=时为，在0j为0。 且该算法的特点是：随着包中物品的加入，包中容量也随之不断在变化，每次包中放物品前都基于包中剩余的容量，当达到最优解时，此时包不一定都装满。该算法所需的算法的计算时间复杂性为O()，若所给物品重量是整数时，该算法的计算时间复杂性为O(minnc,).（2）.实验结果为：总共装进背包的容量是1000；装进背包物品的总价值为3076。.贪心算法（1）.贪心算法在解决问题的时候，总是做出当前看来是最好的选择，并不从整体上最优加以考虑。在做出局部意义上的最优选择之后，我们能得到一个近似的最优解，即使它不一定是最优的，但在要求不那么精确地情况下，往往能较为便捷地得到结果。贪心算法求解背包问题的步骤:首先计算每种物品单位重量的价值vi/wi；然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。(2). 实验结果为：装入背包的物品总价值为：3087。（3）结果分析：使用贪心算法，时间复杂度为O（n*logn）。优于动态规划算法，空间占有也较动态规划少，但贪心算法所得得结果并不一定是最优解。. 回溯法（1）. 问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。 （2）. 回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 （3）.算法设计步骤： a. 针对所给问题，定义问题的解空间； b. 确定易于搜索的解空间结构； c. 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；（4）. 实验结果：装入背包物品的总价值为：3090。（5）.结果分析：回溯法在最坏的情况下有O()个右儿子节点需要计算上界，且计算上界的时间为O（n），所以回溯法时间复杂度为O（n*)。而且对空间复杂性分析来说，该算法需要栈来存储中间值，故空间复杂度大。同时随着问题规模的扩大，会使得问题处理起来的时间花销增大，故而构建良好的剪枝函数成为回溯法的关键所在。但由于回溯法德适应性比较好，很多问题的解决也都会采用它。. 分支界限法（1）. 分支限界法运用优先队列扩展了活结点的运行空间。使得算法在广域中可以较为快捷的剪掉冗余枝。整个解空间较之于回溯法是快速聚类的，故其时间复杂度较回溯法优，但在空间上却需要相当一部分的处理能力。对于离散的最优化方法较为适宜，这是分支法好处，却也是其局限所在。（2）. 算法设计步骤：a. 各物品按性价比有大到小排序，构建解空间树；b. 由根节点出发，检查当前左儿子结点的可行性，如果可行，将它加入到子集树和活动队列中；c. 仅当右儿子结点满足上界约束，才将它加入子集树和活结点优先序列。d. 重复b,c 至整个解空间结束。（3）. 实验结果：装入背包的物品的总价值为：3027。专心-专注-专业
