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

实验报告13课程 数据结构与算法 实验名称 分支限界法 第 页班级 11计本 学号 105032011130 姓名 风律澈 实验日期：2013年6月3日 报告退发 (订正 、 重做) 一、实验目的掌握分支限界法的原理和应用。二、实验环境1、微型计算机一台 2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、实验内容 必做题：1、 编写程序，采用分支限界法求解单元最短路径问题。2、 编写程序，采用分支限界发法实现0-1背包问题。四、实验步骤和结果(附上代码和程序运行结果截图)1,单源最短路径import java.util.PriorityQueue;public class BBShortest /* * param args */static class HeapNode implements Comparableint i;/顶点编号int length;HeapNode(int ii,int ll)/构造函数，类种类i=ii;length=ll;Overridepublic int compareTo(Object o) /为优先队列设置优先级判定方法/ TODO Auto-generated method stubint x=(HeapNode)o).length;if(lengthx) return -1;if(length=x) return 0;return 1;static int a;/图的邻接矩阵public static void shortest(int v,int dist,int p)int n=p.length-1;PriorityQueue heap=new PriorityQueue();/生成一个优先队列存放活节点HeapNode enode=new HeapNode(v,0);for(int j=1;j=n;j+)distj=Integer.MAX_VALUE;/默认每个顶点初始都是最长距离distv=0;while(true)for(int j=1;j=n;j+)if(aenode.ijInteger.MAX_VALUE&enode.length+aenode.ijdistj)/约束条件，有连通&可能存在更有解distj=enode.length+aenode.ij;/更改点j的最优路径pj=enode.i;/把这个成为解的编号写入存放结果的数组p中HeapNode node=new HeapNode(j,distj);heap.add(node);/加入活结点优先队列if(heap.isEmpty()break;elseenode=heap.poll();public static void main(String args) / TODO Auto-generated method stubint M=Integer.MAX_VALUE;a=new intM,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;int v = 1;int dist=new inta.length;int p=new inta.length;shortest(v,dist,p);for(int i=1;idist.length;i+)System.out.print(disti+ );-2，0-1背包问题package bag01b;import java.util.ArrayList;public class bag01do /* * param args */public static void main(String args) / TODO Auto-generated method stubArrayList objects=new ArrayList();objects.add(new object(3,9);objects.add(new object(5,10);objects.add(new object(2,7);objects.add(new object(1,4);bag b=new bag(7,objects);b.findmaxvalue();b.show();-package bag01b;import java.util.ArrayList;import java.util.Collections;import java.util.PriorityQueue;public class bag private int bagv; private ArrayList objects; private int maxvalue; private ArrayList result_objects; public bag(int v,ArrayList o) super(); this.bagv=v; this.objects=o; this.maxvalue=0; this.result_objects=null; Collections.sort(objects); public void show() System.out.println(maxvalue :+ this.maxvalue); System.out.println(the object when maxvalue:+this.result_objects); public void findmaxvalue() PriorityQueue enode=new PriorityQueue(); Node node=new Node(0,null,bagv,this.objects); enode.offer(node); while(true) if(enode.isEmpty() break; node=enode.poll(); if(node.isend() this.maxvalue=node.get_bag_value(); this.result_objects=new ArrayList(node.get_in_bag_object(); return; int i=node.get_node_in(); object iobject=this.objects.get(i); if(node.get_bag_weight()+iobject.getweight()=this.bagv) ArrayList newnodeinbag=new ArrayList(node.get_in_bag_object(); newnodeinbag.add(iobject); int newnodebagv=node.get_bag_leftv()-iobject.getweight(); Node newnode=new Node(i+1,newnodeinbag,newnodebagv,this.objects); enode.add(newnode); if(newnode.get_bag_value()this.maxvalue) this.maxvalue=newnode.get_bag_value(); this.result_objects=new ArrayList(newnode.get_in_bag_object(); Node newnode=new Node(i+1,node.get_in_bag_object(),node.get_bag_leftv(),this.objects); if(newnode.get_bag_prio()this.maxvalue) enode.add(newnode); -package bag01b;import java.util.ArrayList;public class Node implements Comparableprivate int node_in;private ArrayList inbag_object;private ArrayList outbag_object;private int leftv;private int prio;public Node(int i,ArrayList in,int l,ArrayList out)super();this.node_in=i;if(in=null)in=new ArrayList();this.inbag_object=in;this.leftv=l;this.outbag_object=out;this.prio=this.find_prio();private int find_prio() / TODO Auto-generated method stubint bag_left=this.leftv;int p=this.get_bag_value();int i=this.node_in;object iobject=null;while(true)if(i=this.inbag_object.size()break;iobject=this.inbag_object.get(i);if(iobject.getweight()bag_left)break;bag_left-=iobject.getweight();p+=iobject.getvalue();i+;if(io.prio) return -1;if(this.prioo.prio) return 1;return 0;public boolean isend()if(this.node_in=this.outbag_object.size()return true;elsereturn false;public ArrayList get_in_bag_object()return this.inbag_object;public int get_node_in()return this.node_in;public int get_bag_leftv()return this.leftv;public int get_bag_prio()return this.prio;public String toString()return node in+this.node_in+node prio+this.prio;-package bag01b;public class object implements Comparableprivate static int ids=1;private int id;private int weihgt;private int value;public object(int w,int v)super();this.weihgt=w;this.value=v;this.id=ids+;public int getid()return this.id;public int getweight()return this.weihgt;public int getvalue()return this.value;public float getvw()return (flo