package demo1;

/**
 * 分支限界FIFO
 * 
 */
public class BranchLimitFIFOSearch {

	public static void main(String[] args) {
		// n个货箱
		int n = 3;
		// 第一艘船的载重量
		float c1 = 50;
		// 第二艘船的载重量
		float c2 = 50;
		// 货箱质量数组
		float[] w = { 0, 10, 40, 40 };

		// 初始化
		BranchLimitFIFOSearch bfis = new BranchLimitFIFOSearch(n, c1, c2, w);
		// 所有货箱的重量之和
		float s = bfis.getS();
		if (s <= c1 || s <= c2) {
			System.out.println("只需要1首船！");
		}
		if (s > c1 + c2) {
			System.out.println("2首船不能解决问题！");
			return;
		}
		// 获取最大装载
		bfis.maxLoading(c1);
		// 第一艘船的最大装载
		float bestw = bfis.getBestw();

		if (s - bestw <= c2) {
			System.out.println("第1首船装载： " + bestw);
			System.out.println("第2首船装载： " + (s - bestw));
		} else {
			System.out.println("不能解决问题");
		}

	}

	private int n; // n个货箱
	private float c1; // 第一艘船的载重量
	private float c2; // 第二艘船的载重量
	private float bestw; // 第一艘船的最大装载
	private float ew = 0; // 当前船的装载量
	private float[] w; // 货箱质量数组
	private float s = 0; // 所有货箱的重量之和
	private MyQueue mq = new MyQueue(); // FIFO队列，活动队列

	/**
	 * 构造方法
	 * 
	 * @param _n
	 * @param _c1
	 * @param _c2
	 * @param _w
	 */
	public BranchLimitFIFOSearch(int _n, float _c1, float _c2, float[] _w) {
		n = _n;
		c1 = _c1;
		c2 = _c2;
		w = _w;
		for (float f : _w) {
			s += f;
		}
	}

	/**
	 * 最优装载值
	 * 
	 * @param c
	 *            第1首船的载重量
	 */
	public float maxLoading(float c) {
		// 初始化结点队列，标记分层
		// -1：每一层处理完，都以-1为标记
		mq.put(new Float(-1));
		// A结点的层
		int i = 1;
		// 当前船的装载量
		ew = 0;
		// 目前的最优值
		bestw = 0;
		// 搜索子集空间树
		while (!mq.empty()) {
			// 检查A结点的左孩子，货箱i是否可以装载
			// ew船目前载重量
			// 符合条件放到活动队列中
			if (ew + w[i] <= c) {
				// 货箱i可以装载
				addLiveNode(ew + w[i], i);
			}
			// 右孩子总是可行的，不装载货物i
			addLiveNode(ew, i);
 			// 获取活动队列
			ew = (Float) mq.get();
			// 到达层的尾部，每层的结束
			if (ew == -1) {
				// 活动队列没有数据，则返回最优解
				if (mq.empty()) {
					return bestw;
				}
				// 处理完当前层，标记-1
				mq.put(new Float(-1));
				// 获取活动队列的下一个节点，表示船的载重量
				ew = (Float) mq.get();
				i++; // ew的层
			}
		}
		return bestw;
	}

	/**
	 * 入队
	 * 
	 * @param wt
	 * @param i
	 */
	public void addLiveNode(float wt, int i) {
		if (i == n) { // 是叶子
			// 最大重量
			if (wt > bestw) {
				bestw = wt;
			}
		} else { // 不是叶子
			// 添加到队列中
			mq.put(new Float(wt));
		}
	}

	public int getN() {
		return n;
	}

	public void setN(int n) {
		this.n = n;
	}

	public float getC1() {
		return c1;
	}

	public void setC1(float c1) {
		this.c1 = c1;
	}

	public float getC2() {
		return c2;
	}

	public void setC2(float c2) {
		this.c2 = c2;
	}

	public float getBestw() {
		return bestw;
	}

	public void setBestw(float bestw) {
		this.bestw = bestw;
	}

	public float getEw() {
		return ew;
	}

	public void setEw(float ew) {
		this.ew = ew;
	}

	public float getS() {
		return s;
	}

	public void setS(float s) {
		this.s = s;
	}

}

package demo1;

import java.util.LinkedList;

/**
 * 自定义活动队列
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.25
 * 
 */
public class MyQueue {
	private LinkedList ll = new LinkedList();

	/**
	 * 入队
	 * 
	 * @param o
	 */
	public void put(Object o) {
		ll.addLast(o);
	}

	/**
	 * 出队
	 * 
	 * @return
	 */
	public Object get() {
		return ll.removeFirst();
	}

	/**
	 * 队是否为空
	 * 
	 * @return
	 */
	public boolean empty() {
		return ll.isEmpty();
	}
}