回溯法、分支限界法解0-1背包问题(计算机算法设计与分析实验报告)

1、实验报告课程名称： 算法设计与分析 实验名称：回溯法、分支限界法解0-1背包问题 任课教师：张锦雄 专 业： 计算机科学与技术班 级：2007 级1班 学 号：姓 名：蓝冠恒 完成日期： 2011 年1月12日、实验目的：掌握回溯法、分支限界法的原理，并能够按其原理编程实现解决0-1背包问题，以加深对回溯法、分支限界法的理解。二、主要实验内容及要求：1 要求分别用回溯法和分支限界法求解0-1背包问题；2 要求交互输入背包容量，物品重量数组，物品价值数组；3.要求显示结果。三、实验环境和工具：操作系统:win7操作系统开发工具：eclipse34 jdk1.6开发语言：java四、实验结果与结论

2、：（经调试正确的源程序和程序的运行结果）1.1、回溯法求解0-1背包问题源代码：package cn.l gh;import java.io.BufferedReader;import java.i o.ln putStreamReader;import java.util.Arrays;import java.util.Comparator;/*回溯法解0-1背包问题。* author 蓝冠恒*/public class BTKn apsack double c; / 背包重量int n; / 物品总数double w; / 物品重量数组double p; / 物品价值数组doublecw;

3、/当前重量doublecp ;/当前价值doublebestp ;/ 当前最优价值/*回溯法解0- 1背包问题。*parampp*物品价值数组*paramww*物品重量数组*paramcc*背包重量*return最优价值*/public doublekn apsack(double pp, double ww, double cc) c = cc;n = pp.len gth;cw = 0.0;cp = 0.0;bestp = 0.0;Eleme nt q =new Eleme nt n;for ( int i = 0; i <n; i+) qi = new Eleme nt(i + 1

4、, ppi / wwi);Arrays. sort (q, new ElemComparator();p = new double n + 1;w = new double n + 1;for ( int i = 1; i <=n; i+) pi = ppqi - 1.id - 1;wi = wwqi - 1.id - 1;backtrack(1);return bestp ;/回溯过程private void backtrack( int i) if (i > n) / 达到叶节点bestp = cp;return ;if ( cw + wi <= c) cw +=wi;c

5、p +=pi；backtrack(1 + i);cw -=wi;cp -=pi；if (bound(i + 1) >bestp ) backtrack(1 + i);/计算上界值private double bou nd( int i) double cleft = c - cw;doublebound = cp ;/以物品单位重量价值递减顺序装入物品while (i <= n && wi <= cleft) cleft -=wi;bou nd +=pi;i+;/装满背包if (i <= n) bou nd += pi * cleft /wi;retur

6、 nbou nd;*物体编号和单位重量价值载体。* author 蓝冠恒*/publicclassEleme nt intid ; / 编号double d; /单位重量价值publicEleme nt(int id, double d) this . id = id;this . d = d;/*比较器author 蓝冠恒*/ public class ElemComparator impleme nts Comparator<Object> public int compare(Object object1, Object object2) Element element1 =

7、 (Element) object1;Element element2 = (Element) object2;if (eleme nt1. d < eleme nt2.d) return 1; else return 0;public static void main( Stri ng args) String in put;Stri ng flag;double capacity = 0;double pp;double ww;double bestP=0.0;BTKn apsack btK napsack=new BTKn apsack();BufferedReader in =

8、new BufferedReader( new InputStreamReader(System.in );do try do System. out .println("请选择数字功能键：1-输入数据，2-退岀系统":flag = in .readL in e().trim();while (!(flag.equals("1" ) | flag.equals("2");if(flag.equals("2" ) Ibreak ; doSystem. out .println("请输入各物品重量，数据之间必

9、须以顿号间隔分开！“in put = in. readL in e().trim();in put = in. readL in e().replaceAll("" "" ); while(input.equals("");if (input.equals("2" )break ;String datas = input.split("、");int n1 = datas. len gth ;pp= new double n 1;ww=new double n 1;for (int i = 0;

10、 i < n1; i+) wwi= Double. parseDouble (datasi);do System. out .println(”请输入各物品价值，数据之间必须以顿号间隔分开！");in put = in. readL in e().trim();in put = in .readLi ne().replaceAll("",""); while(input.equals("");if (input.equals("2" )break ;datas= input.split("

11、、");int n2 = datas. len gth ;if (n 1!=n2)System. out .println( ”输入数据个数不一致，重新输入")；con ti nue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble (datasi);do System. out .println("请输入背包的容量：")；in put = in. readL in e().trim();in put = in .readLi ne().replaceAll("","

12、;"); while(input.equals("");if (input.equals("2" )break ;capacity=Double. parseDouble (in put);bestP=btK napsack.k napsack(pp, ww, capacity);System. out .println("回溯法解得最优价值："+bestP); catch(Exception e) e.pri ntStackTrace(); while ( true );单B1.2、运行结果:X 禺貶剧列cJ S - C3

13、<termirated> BTKnapsack Java Applkaticn E：n$tallS请输入各物品重量，数据之间必须以顿号间隔分开!请选择数字功能键：】一输入数擔，"退岀系统请输入各物品重量，数据之间必须以顿号间隔分开!2.1、分支限界法求解0-1背包问题源代码:Problems ® Javadocpackage import import import器蠶務缁if；二訣数瘗2退出系统cn .Igh; java.io.BufferedReader; java.i o.ln putStreamReader; java.util.Arrays;请选择数字

14、功能键：1一输入数据，2退出系统/*分支界限法解0- 1背包问题。* author 蓝冠恒loo y 120 x eo 请输入背包的容量:50、40 x IS x 2S > 10请输入各物品价值，数振之间必须以顿号间隔分幵!250 x 80 > 45 > 100 > 20请输入背包的W1：2032 x 10 > 18请输入各物品价值，数擔之间必须以顿号间隔分开!B0回洌法解得最优恰值：35.0 请选择数字功能键：1输入数据，2退出系统|J BTKrrap sack Java S3=臣 Outline 克nackaae cn,lah:凫Q疋0 P 亠一 “”、彳l&

15、#187;L.Declaration 貝 Console S3 '*/public classBBK napsack double c; /背包重量int n; / 物品总数doublew;/物品重量数组doublep;/物品价值数组doublecw;/当前重量doublecp ;/当前价值int bestxJ/最优解MaxHeap maxHeap = new MaxHeap(); /活节点优先队列/计算节点所对应的节点的上界private double bou nd( int i) double cleft = c - cw;double b = cp ;/以物品单位重量价值递减装填

16、剩余容量while (i <= n && wi <= cleft) cleft -=wi;b +=pi;i+;/装填剩余容量装满背包if (i <= n) b += pi / wi * cleft;return b;/添加新的活节点到子集树和优先队列中private void addLiveNode( double upperProfit,double pp, double ww,int level, BBnode pare nt,boolea nleftChild) BB node b =new BB node(pare nt, leftChild);Hea

17、pNode node = new HeapNode(b, upperProfit, pp, ww, level); maxHeap .put(node);/优先队列式分支界限法private doublebbK napsack() BBnode enode = n ull ;int i = 1;double bestp = 0.0;double up = bou nd(1);while (i != n + 1) double wt = cw +wi;/检查当前扩展节点的左儿子节点if (wt <= c) if ( cp + pi > bestp) bestp = cp +pi;ad

18、dLiveNode(up,cp + pi, cw + wi, i + 1, eno de,true );up = bou nd(i + 1);/检查当前扩展节点的右儿子节点if (up >= bestp) addLiveNode(up, cp , cw, i + 1, eno de,false );HeapNode node = maxHeap .removeMax();enode = no de. liveNode ;cw = no de.weight ;cp = no fit;up = no de.upperProfit ;i = no de.level ;/构造当前最优

19、解for ( int j = n; j > 0; j-) bestx j = (eno de.leftChild ) ? 1 : 0;enode = eno de.pare nt;return cp;*将个物体依其单位重量价值从大到小排列，然后调用bbKnapsack完成对子集树优先队列式分支界*限搜索。* return 最优解*/public double knapsack(double pp, double ww, double cc, int xx) c = cc;n = pp. len gth ;Eleme nt q =new Eleme ntn;double ws = 0.0;

20、double ps = 0.0;for ( int i = 0; i <n; i+) qi = new Eleme nt(i + 1, ppi / wwi); ps += ppi;ws += wwi;if (ws <= c) for ( int i = 1; i <=n; i+) xxi = 1;return ps;/依单位重量价值排序Arrays. sort (q,newElemComparator();p =new double n + '1;w =new double n + '1;for(int i = 1; i <=n; i+) pi = pp

21、qi - 1.id - 1;wi = wwqi - 1.id - 1;cw = 0.0;cp = 0.0;bestx = new int n + 1; maxHeap = new MaxHeap();/ 调用bbKnapsack 求问题的最优解 double maxp = bbK napsack();for (int i = 1; i <=n; i+) xxqi - 1.id - 1 = bestx i;return maxp;public static void main( Stri ng arg) String in put;Stri ng flag;double capacity

22、= 0;double pp;double ww;int xx;double bestP=0.0;BBK napsack bbK napsack=new BBK napsack();BufferedReader do in = new BufferedReader(new InputStreamReader(System.in )；trydo System. out .println( flag = in .readL in e().trim(); while (!(flag.equals("请选择数字功能键:"1" ) | flag.equals(1-输入数据，2

23、-退岀系统“);"2");if (flag.equals( break ;do "2" ) System. out .println("请输入各物品重量,数据之间必须以顿号间隔分开!);in put = in .readLi ne().trim();in put = in .readLi ne().replaceAll(I! I!III!); while (input.equals("");if (input.equals("2" )breakString datas = input.split(&quo

24、t;、");int n1 = datas. len gth ;pp= new double n 1;ww=new double n 1;for (int i = 0; i < n1; i+) wwi= Double. parseDouble (datasi);do System. out .println("请输入各物品价值,数据之间必须以顿号间隔分开!);in put = in .readLi ne().trim();in put = in .readLi ne().replaceAll(I! I!III!); while (input.equals("&

25、quot;);if (input.equals("2" )break ;datas= input.split("、");int n2 = datas.len gth;if (n 1!=n2)System. out .println("输入数据个数不一致，重新输入");con ti nue;for (int i = 0; i < n1; i+) ppi= Double.parseDouble (datasi);do System. out .println("请输入背包的容量：")；in put = in. r

26、eadL in e().trim();in put = in .readLi ne().replaceAll("",""); while (input.equals("");if (input.equals("2" )break ;xx= new int n 1;capacity=Double. parseDouble (in put);bestP=bbK napsack.k napsack(pp, ww, capacity, xx);System. out .println( "分支界限法法解得最优价值

27、："+bestP);System. out .println( "各个被装入物品情况(1表示被装入，0表示未被装入)：");for (int i = 0; i < n1; i+) System. out .print(xxi+"");System. out .println( "n"); catch (Exception e) e.pri ntStackTrace(); while ( true );packagecn.l gh;/*分支界限节点* author 蓝冠恒*/public class BBnode BBn

28、ode parent ; / 父节点booleanleftChild ; / 左孩子标识publicBBn ode( BBnode pare nt,boolea nleftChild) this . pare nt=pare nt;this . leftChild =leftChild;packagecn.l gh;import java.util.Comparator;/* Eleme nt 对象比较器* author 蓝冠恒*/public class ElemComparator impleme nts Comparator<Object>public int compare

29、(Object objects Object object2) Eleme nt eleme nt1 = (Eleme nt)object1;Eleme nt eleme nt2 = (Eleme nt)object2;if (eleme nt1.d < eleme nt2.d) return 1; else return 0;package cn.l gh;/*物品编号和单位重量价值载体。* author 蓝冠恒*/public class Eleme nt int id ; /物品编号double d; /单位重量价值publicEleme nt(int id, double d)

30、this . id =id;this . d=d;package cn.l gh;import java.util.Comparator;/*堆节点比较器。* author 蓝冠恒*/public class HeapComparatorimpleme ntsComparator<Object>public int compare(Object objectl, Object object2) HeapNode heapNodel = (HeapNode)objectl;HeapNode heapNode2 = (HeapNode)object2;if (heapNode1. up

31、perProfit < heapNode2. upperProfit ) return 1; else return 0;package cn.l gh;/*堆节点* author 蓝冠恒*/public class HeapNode BBn ode liveNode;/活节点doubleupperProfit;/节点价值上限doubleprofit ;:/节点所对应的价值doubleweight ;:/节点所对应的重量int level ; /活节点在子集树中所处的层次序/构造方法publicHeapNode(BB node liveNode,double upperProfit,do

32、uble profit,double weight, int level) this . liveNode = liveNode;this . upperProfit = upperProfit;this . profit = profit;this . weight = weight;this . level = level;import java.util.List;/*装载和管理HeapNode对象。* author 蓝冠恒*/public class MaxHeap /堆节点容器private List<HeapNode> heap =new ArrayList<HeapNode>(); public void put(HeapNode heapNode)he