分支限界算法之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 Comparable{
int i;//顶点编号
int length;

HeapNode(int ii,int ll){//构造函数，类种类
i=ii;
length=ll;
}
@Override
public int compareTo(Object o) {//为优先队列设置优先级判定方法
// TODO Auto-generated method stub
int x=((HeapNode)o).length;
if(length<x) 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<HeapNode> heap=new PriorityQueue<HeapNode>();//生成一个优先队列存放活节点
HeapNode enode=new HeapNode(v,0);
for(int j=1;j<=n;j++)
dist[j]=Integer.MAX_VALUE;//默认每个顶点初始都是最长距离
dist[v]=0;

while(true){
for(int j=1;j<=n;j++)
if(a[enode.i][j]<Integer.MAX_VALUE&&enode.length+a[enode.i][j]<dist[j]){//约束条件，有连通&&可能存在更有解
dist[j]=enode.length+a[enode.i][j];//更改点j的最优路径
p[j]=enode.i;//把这个成为解的编号写入存放结果的数组p中
HeapNode node=new HeapNode(j,dist[j]);
heap.add(node);//加入活结点优先队列
}
if(heap.isEmpty())
break;
else
enode=heap.poll();
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int M=Integer.MAX_VALUE;
a=new int[][]{
{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}
};
int v = 1;
int dist[]=new int[a.length];
int p[]=new int[a.length];
shortest(v,dist,p);
for(int i=1;i<dist.length;i++){
System.out.print(dist[i]+" ");
}
}

}
--------------------------------------------------------------------

-------------------------------------------------------------------------------------------------------------------------------------------
2，0-1背包问题
package bag01b;

import java.util.ArrayList;

public class bag01do {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<object> 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<object> objects;
private int maxvalue;
private ArrayList<object> result_objects;

public bag(int v,ArrayList<object> 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<Node> 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<object> newnodeinbag=new ArrayList<object>(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 Comparable<Node>{
private int node_in;
private ArrayList<object> inbag_object;
private ArrayList<object> outbag_object;
private int leftv;
private int prio;
public Node(int i,ArrayList<object> in,int l,ArrayList<object> 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 stub
int 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(i<=this.inbag_object.size()-1)
p+=iobject.getvw()*bag_left;
return p;
}
public int get_bag_weight(){
int w=0;
for(object o:this.inbag_object){
w+=o.getweight();
}
return w;
}
public int get_bag_value(){
int w=0;
for(object o:this.inbag_object){
w+=o.getvalue();
}
return w;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
if(this.prio>o.prio) return -1;
if(this.prio<o.prio) return 1;
return 0;
}
public boolean isend(){
if(this.node_in==this.outbag_object.size())
return true;
else
return false;
}
public ArrayList<object> 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 Comparable<object>{
private 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 (float)this.value/this.weihgt;}
@Override
public int compareTo(object o) {
// TODO Auto-generated method stub
if(this.getvw()>o.getvw()) return -1;
if(this.getvw()<o.getvw()) return 1;
return 0;
}

public String toString(){
return "object "+this.id+" ";
}

}
-----------------------------------------------------------------------

五、实验总结
(本次实验完成的情况，心得体会)