fac6_3.java

//本程序取自王晓东编著“算法分析与设计”第 198 页

//本程序取自王晓东编著“算法分析与设计”第 198 页，例
//装载问题的分支限界解法

class Element implements Comparable
{

    int w;
    int id;

    public Element(int ww, int ii)
    {
        w = ww;
        id = ii;
    }

    public int compareTo(Object x)
    {
        int xw = ((Element) x).w;
        if (w < xw) {
            return -1;
        }
        if (w == xw) {
            return 0;
        }
        return 1;
    }
}

class AQueue
{

    private static final int defultSize = 20;
    private int size;                     //
    private int front;
    private int rear;
    private Element[] listArray;

    AQueue()
    {
        setup(defultSize);
    }

    AQueue(int sz)
    {
        setup(sz);
    }

    void setup(int sz)
    {
        size = sz + 1;
        front = rear = 0;
        listArray = new Element[sz + 1];
    }

    public void clear()
    {
        front = rear = 0;
    }

    public static void Assert_notFalse(boolean p, String q)
    {
        if (!p) {
            System.out.println((String) q);
        }
    }

    public void enqueue(Element it)
    {
        Assert_notFalse(((rear + 1) % size) != front, "Queue is full");
        rear = (rear + 1) % size;
        listArray[rear] = it;
    }

    public Element remove()
    {
        Assert_notFalse(!isEmpty(), "Queue is empty ");
        front = (front + 1) % size;
        return listArray[front];
    }

    public Element firstValue()
    {
        Assert_notFalse(!isEmpty(), "Queue is empty ");
        return listArray[(front + 1) % size];
    }

    public boolean isEmpty()
    {
        return front == rear;
    }

    public void put(int k, int g)
    {
        Element itg = new Element(k, g);
        enqueue(itg);
    }
}//class AQueue

class FIFOBBloding
{

    static int n;            // 表示最大层数，即集装箱个数
    static int bestw;        // 当前最优载重量
    static AQueue queue;     //活结点队列
//    public void FIFOBBloding()
//    {
//        n = 11;
//    }

    public  int maxLoading(int[] w, int c)
    {// 队列式分支限界法，返回最优载重量
        // 初始化
        n = w.length - 1;//货物个数Qkw
        bestw = 0;
        queue = new AQueue();
        queue.put(1, -1);  //同层结点尾部标志

        int i = 1;                     //当前扩展结点所处的层
        int ew = 0;                    //扩展结点所相应的载重量

//        for (int iii = 0;iii< 11; iii++) {
//            System.out.println("w[" + iii + "]=" + w[iii] + " ");
//        }//测试用Qkw
        

        //搜索子集空间树
        while (true)
        {
            //检查左儿子结点
            if (ew + w[i] <= c)//x[i]=1
            {

       
                enQueue(ew + w[i], i);//

            }
            //右儿子结点总是可行的
            enQueue(ew, i);                        //x[i]=0


            ew = queue.remove().w; //取下一扩展结点

            if (ew == -1)
            {//同层结点尾部
                System.out.println("ew= "+ew);
                if (queue.isEmpty())
                {
                    return bestw;
                }
                queue.put(i, -1);        //同层结点尾部标志
                ew = queue.remove().w;  //取下一扩展结点
                i++;    //进入下一层
            }
  
        }
    }

    private static void enQueue(int wt, int i)
    {//将活结点加入到活结点队列Q中
        if (i == n)
        {//可行叶结点
            if (wt > bestw)
            {
                bestw = wt;
            }
        } else //非叶结点
        {
            queue.put(i, wt);
        }
    }
}

public class Fac6_3 {

    public static void main(String args[])
    {

        FIFOBBloding abc = new FIFOBBloding();

        int ca = 5000;

        int wa[] = {0, 100, 200, 303, 678, 975, 123, 880, 2400, 1300, 1500};

        int n1 = wa.length;

        int xa[] = new int[n1];

        System.out.println("输出原始数据：第一艘轮船载重c=" + ca);
        for (int i = 0; i < n1; i++) {
            System.out.println("w[" + i + "]=" + wa[i] + " ");
        }


        System.out.print("轮船承载最大价值 opt= ");

        System.out.println(abc.maxLoading(wa, ca));

        System.out.println("所选集装箱序列  ");
        for (int k = 0; k < n1; k++) {
            if (xa[k] == 0) {
                break;
            }
        }
        System.out.println("  ");

    }
}