0-1背包问题实验报告.docVIP

0-1背包问题实验报告 一．问题描述 给定n种物品和一个背包。物品i的重量是w[i]，其价值为v[i]，背包容量为c。 问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。 在选择装入背包的物品时，对每种物品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,1} 每个物品价值分别为： {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背包问题，在给定c0, 0，0，1=i=n，要求找出一个n元0-1向量（x1,x2,…,xn）， {0，1},1≤i≤n；使得，而且。 同时可得出其递推关系，设最优值m[i,j]是背包容量为j，可选物品i,i+1…,n时0-1背包问题的最优值。于是可建立计算m(I,j)的递归式： m[i,j]在j=,为max{m(i+1,j),m(i+1,j-)+}, 在0=j时，m(i+1,j); m[n,j]在j=时为，在0≤j≤为0。 且该算法的特点是：随着包中物品的加入，包中容量也随之不断在变化，每次包中放物品前都基于包中剩余的容量，当达到最优解时，此时包不一定都装满。该算法所需的算法的计算时间复杂性为O()，若所给物品重量是整数时，该算法的计算时间复杂性为O(min{nc,}). （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*)。而且对空间复杂性分析来说，该算法需要栈来存储中间值，故空间复杂度大。同时随着问题规模的扩大，会使得问题处理起来的时间花销增大，故而构建良好的剪枝函数成为回溯法