01背包问题不同算法设计分析与对比.doc

实验三01背包问题不同算法设计、分析与对比一. 问题描述给定n种物品和一背包物品i的重量是w，其价值为Vi,背包的容量为c 问题：应如何选择装入背包中的物品，使得装入背包中物品的总价值最大说明：在选择装入背包的物品时，对每种物品i只有两个选择，装入背包或不装入背包，也不能将物品装入背包多次二. 实验内容与要求实验内容：1. 分析该问题适合采用哪些算法求解(包括近似解)动态规划、贪心、回溯和分支限界算法2. 分别给出不同算法求解该问题的思想与算法设计，并进行算法复杂性分析动态规划：递推方程：m(i,j) = max{m(i-1,j),m(i-1,j-wi)+vi} j >= wi;m(i-1,j) j < wi;时间复杂度为0(n).贪心法：算法思想：贪心原则为单位价值最大且重量最小，不超过背包最大承重量 为约束条件也就是说，存在单位重量价值相等的两个包， 则选取重量较小的那个背包但是，贪心法当在只有在解决物品可以分割的背包问题时是正确的 贪心算法总是作出在当前看来最好的选择也就是说贪心算法并不从整体最优考 虑，它所作出的选择只是在某种意义上的局部最优选择用贪心法设计算法的特点是一步一步地进行，根据某个优化测度(可能是目 标函数，也可能不是目标函数)，每一步上都要保证能获得局部最优解。

每一步 只考虑一个数据，它的选取应满足局部优化条件若下一个数据与部分最优解连 在一起不再是可行解时，就不把该数据添加到部分解中， 直到把所有数据枚举完，或者不能再添加为止回溯法：回溯法：为了避免生成那些不可能产生最佳解的问题状态， 要不断地利用限 界函数(bounding function) 来处死那些实际上不可能产生所需解的活结点， 以 减少问题的计算量这种具有限界函数的深度优先生成法称为回溯法对于有n种可选物品的0/1背包问题，其解空间由长度为n的0-1向量组成， 可用子集数表示在搜索解空间树时，只要其左儿子结点是一个可行结点， 搜索 就进入左子树当右子树中有可能包含最优解时就进入右子树搜索时间复杂度为：0(2 n)空间复杂度为：O(n)分支限界算法：|首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行 排列在优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的 最大单位重量价值的物品装满剩余容量的价值和算法首先检查当前扩展结点的左儿子结点的可行性如果该左儿子结点是可 行结点，则将它加入到子集树和活结点优先队列中 当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优 先队列。

当扩展到叶节点时为问题的最优值3. 设计并实现所设计的算法4. 对比不同算法求解该问题的优劣这动态规划算法和贪心算法是用来分别解决不同类型的背包问题的， 当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大 到小取即可 当一件背包物品不可分割的时候，(因为不可分割，所以就算按 物品的单位体积的价值大的先取也不一定是最优解)此时使用贪心是不对的，应 使用动态规划设计方法时间复杂度优点缺点动态规划Min{nc，2n}可求得最优决策序列速度慢贪心方法O(2n)速度较快很难得到最优解回溯法O(n2n)能够得到最优解时间复杂度较咼分支限界法O( 2n)速度较快，易求解占用内存大，效率不咼5. 需要提交不同算法的实现代码和总结报告动态规划方法：args ) {public class Kn apsack {public static void main( Stri ng[] int [] value = { 0, 60, 100, 120 };int [] weigh = { 0, 10, 20, 30 };int weight = 50;Knapsack1 (weight , value , weigh );publicstaticvoid Kn apsack1(int weight , int [] value,int []weigh )int[]v =new int[value .len gth ];int[]w =new int[weigh .len gth ];int[][] c = new int [ value.length][weight + 1];intd[]=new int[100];for(inti = 0; i< value.length;i ++) {v[i ]=value [ i];} forw[ i ]=weigh [ i];(inti = 1; i< value.length;i ++) {for (int k = 1;k <=weight ;k++) {if(w[ i ]<=k) {c[ i ][ k]=max(c[i - 1][k], c[ i - 1][ k -w[i ]] +v[ i ]);{} else {c[ i ][ k] = c[ i - 1][ k];}}}System. out .println( c[ value . length - 1][ weight ]);}private static int max( int i , int j ) {int k = i > j ? i : j ;return k;}}贪心法：public class GreedyK napSack {publicstatic void main( Stri ng[]args ) {int[] value = { 0, 60,100,120 };int[] weigh = { 0,10, 20, 30 };intweight = 50;Knapsack1 (weight , value , weigh );}private staticvoid Kn apsack1( int weightint [] v, int [] w) {int n = v. length ;double [] r = new double [ n]; int [] index = new int [ n];for ( int i = 0; i < n; i ++) {r [ i ] = ( double ) v[ i ] / ( double ) w[ i ];index [ i ] = i}//按单位重量价值r[i]=v[i]/w[i] 降序排列double temp = 0;for ( int i = 0; i < n-1; i ++){for ( int j = i +1; j < n; j ++){if (r[i] < r [ j ]){temp = r [ i ];r [ i ] = r[j ];r [ j ] = temp ;int x = index [ i ];index [ i ] = index [ j ];index [ j ] = x;}}}//排序后的重量和价值分别存到 w1[]和v1[]中int[]w1 =new int[n ];int[]v1 =new int[n ];for(inti=0; i