分支限界算法之0-1背包问题和单源最短路径问题java源程序

《分支限界算法之0-1背包问题和单源最短路径问题java源程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告13课程数据结构与算法实验名称分支限界法第页班级11计本学号105032011130姓名风律澈实验日期：2013年6月3日报告退发(订正、重做)一、实验目的掌握分支限界法的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统，JavaSDK，Eclipse开发环境三、实验内容必做题：1、编写程序，采用分支限界法求解单元最短路径问题。2、编写程序，采用分支限界发法实现0-1背包问题。四、实验步骤和结果(附上代码和程序运行结果截图)1,单源最短路径importjava.util.PriorityQueue;publicclassBBSh

2、ortest{/***@paramargs*/staticclassHeapNodeimplementsComparable{inti;//顶点编号intlength;HeapNode(intii,intll){//构造函数，类种类i=ii;length=ll;}@OverridepublicintcompareTo(Objecto){//为优先队列设置优先级判定方法//TODOAuto-generatedmethodstubintx=((HeapNode)o).length;if(length

3、0;return1;}}staticint[][]a;//图的邻接矩阵publicstaticvoidshortest(intv,int[]dist,int[]p){intn=p.length-1;PriorityQueueheap=newPriorityQueue();//生成一个优先队列存放活节点HeapNodeenode=newHeapNode(v,0);for(intj=1;j<=n;j++)dist[j]=Integer.MAX_VALUE;//默认每个顶点初始都是最长距离dist[v]=0;while(t

4、rue){for(intj=1;j<=n;j++)if(a[enode.i][j]

5、ak;elseenode=heap.poll();}}publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintM=Integer.MAX_VALUE;a=newint[][]{{M,M,M,M,M,M},{M,0,10,M,30,100},{M,M,0,50,M,M},{M,M,M,0,M,10},{M,M,M,20,0,60},{M,M,M,M,M,0}};intv=1;intdist[]=newint[a.length];intp[]=newint[a.length];sh

6、ortest(v,dist,p);for(inti=1;i

7、-----2，0-1背包问题packagebag01b;importjava.util.ArrayList;publicclassbag01do{/***@paramargs*/publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubArrayList