装载问题-分支限界算法-java实现
5星 · 超过95%的资源 需积分: 43 98 浏览量
2013-01-06
11:25:16
上传
评论 2
收藏 36KB DOC 举报 
/*
* 装载问题-采用分支限界法完成-FIFO方式
* Time：2013-1-6
* 下标从1开始,
* 采用的FIFO的方式，采用remain剪枝的操作,并且采用了string保存了最佳的路径
*/
package com.book.java;
import java.util.*;
public class Project45_FIFOBBloading_2 {
public static int weight[]={0,10,40,40};; //用来表示集装箱中对应的重量
public static int n; //表示数组的个数
public static int bestw; //表示最接近的容量
public static int c; //表示最大的容量
public static Queue<Node45> que;
public static int remain;//用来剪枝的操作的时候使用
public static String bestx;//用来保存最佳的路劲
public static void main(String[] args) {
n=weight.length-1;//初始化个数
c=45; //初始化最大的重量
que=new LinkedList<Node45>(); //初始化FIFO队列
remain=0; //初始化剩余质量，用在剪枝函数
for(int i=1;i<=n;i++)
{
remain=remain+weight[i];
}
fifobbLoading(1);
//输出
System.out.println("最接近最大重量 "+c+" 的重量为:"+bestw);
System.out.println("最佳的路径为"+bestx);
}
public static void fifobbLoading(int num)
{
remain=remain-weight[1];//在第一层进行判断的操作
if(weight[num]<=c) //用于是否需要剪去右枝节
{
Node45 temp=new Node45(weight[num],"1");//初始化右节点
que.offer(temp);
bestw=bestw+weight[num]; //修改最优质量
}
if(remain>=bestw)//用于是否需要剪去左枝节
{
Node45 temp=new Node45(0,"0");//初始化左节点
que.offer(temp);
}
int size=que.size();//初始化在第一层运行结束后队列中的个数
while(num!=n) //判断是否达到最后一层
{
// System.out.println("============================");
// System.out.println("num=="+num);
资源评论
大猪宝贝2013-06-07很不错 对我很有帮助- weiyideyixueyingruo2014-06-25代码对我真的真的很有用，，太及时了，谢了
- 045212015-01-11非常感谢 很有用
