算法 0-1背包问题.doc

《算法 0-1背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、实验目的与要求掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。1．要求分别用回溯法和分支限界法求解0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。二、实验方案在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。三、实验结果和数据处理1．用回溯法解决0-1背包问题：代码：importjava.util.*;publicclassKnapsack{privatedouble[]p,w;//分别代表价值和重量priv

2、ateintn;privatedoublec,bestp,cp,cw;privateintx[];//记录可选的物品privateint[]cx;publicKnapsack(doublepp[],doubleww[],doublecc){this.p=pp;this.w=ww;this.n=pp.length-1;this.c=cc;this.cp=0;this.cw=0;this.bestp=0;x=newint[ww.length];cx=newint[pp.length];}voidKnapsack(){backtrack(0);}voidbacktrack(inti){if

3、(i>n){//判断是否到达了叶子节点if(cp>bestp){for(intj=0;j

4、背包容量：c=7");System.out.println("物品重量数组：w={3,5,2,1}");System.out.println("物品价值数组：p={9,10,7,4}");System.out.println("最优值：="+bestp);System.out.println("选中的物品是:");for(inti=0;i

5、weight=7;Knapsackks=newKnapsack(p,w,maxweight);ks.Knapsack();//回溯搜索ks.printResult();}}运行结果：2．用优先队列式分支限界法解决0-1背包问题：代码：publicclassKnapsack{staticdoublec;staticintn;staticdoublew[];staticdoublep[];staticdoublecw;staticdoublecp;staticintbestX[];staticMaxHeapheap;//上界函数bound计算结点所相应价值的上界privatestatic

6、doublebound(inti){doublecleft=c-cw;doubleb=cp;while(i<=n&&w[i]<=cleft){cleft=cleft-w[i];b=b+p[i];i++;}//装填剩余容量装满背包if(i<=n)b=b+p[i]/w[i]*cleft;returnb;}//addLiveNode将一个新的活结点插入到子集树和优先队列中privatestaticvoidaddLiveNode(doubleup,doublepp,doubleww,intlev,BBnodepar,booleanch){//将一个新的活结点插入到子集树和最大堆中BBnode

7、b=newBBnode(par,ch);HeapNodenode=newHeapNode(b,up,pp,ww,lev);heap.put(node);}privatestaticdoubleMaxKnapsack(){//优先队列式分支限界法，返回最大价值，bestx返回最优解BBnodeenode=null;inti=1;doublebestp=0;//当前最优值doubleup=bound(1);//当前上界while(i!=n+1){//非叶子结点