while (true)
      {                                                                                  
         if (ew + w[i] <= c)        enQueue(ew + w[i], i);      // 检查左儿子结点
         enQueue(ew, i);                                                       //右儿子结点总是可行的
         ew = ((Integer) queue.remove()).intValue();          // 取下一扩展结点
         if (ew == -1)
         {   if (queue.isEmpty())    return bestw;
             queue.put(new Integer(-1));                                // 同层结点尾部标志
             ew = ((Integer) queue.remove()).intValue();      // 取下一扩展结点
             i++;                                                                      // 进入下一层         }    
  }

import java.util.PriorityQueue;

public class Solution {
    // 类数据成员
    static int N;                   // 集装箱数量 - 1
    static int[] best;              // 当前最优解，best[i]表示第i+1个集装箱装载到第best[i]+1艘轮船时最优
    static int[] weight;
    static int[] shipContain;
    static int extendWeight;
    static PriorityQueue<HeapNode> heap;  // 活结点队列
    static int[] remainArr;

    public static void main(String[] args) {
        weight = new int[]{20, 24, 15, 25};     // 每个集装箱重量（从下标1开始）
//        weight = new int[]{10, 20, 36, 25};     // 每个集装箱重量（从下标1开始）
//        weight = new int[]{30, 30, 30, 50, 50, 60};     // 每个集装箱重量
//        shipContain = new int[]{100, 150};             // 两艘轮船的载重量分别为C1，C2

        N = weight.length - 1;
        heap = new PriorityQueue<HeapNode>((a, b) -> b.uweight - a.uweight);
        best = new int[N + 1];
        // 定义剩余重量数组
        remainArr = new int[N + 1];
        for (int i = N - 1; i >= 0; i--) {
            remainArr[i] = remainArr[i + 1] + weight[i + 1];
        }

        System.out.print("集装箱重量分别为：");
        for (int i = 0; i < weight.length; i++) {
            if (i != weight.length - 1) {
                System.out.print(weight[i] + " ");
            } else {
                System.out.println(weight[i]);
            }
        }
        int c1 = 54;
        System.out.println("轮船1最大载重量为" + c1);

        // TODO best[i] = 1 表示装载 0表示为未装载
        System.out.println("轮船1的最优载重量为：" + maxLoading1(weight, c1, best));;
//        System.out.println("集装箱1的最优载重量为：" + maxLoading1(weight, shipContain[0], best));;
//        System.out.println("集装箱2的最优载重量为：" + maxLoading1(weight, shipContain[1], best));;
//        System.out.println(maxLoading1(weight, shipContain[0], best));;
    }

    // TODO 队列式分支限界法
    public static int maxLoading1(int[] w, int c, int[] best) {
        BBnode e = null;        // 当前扩展节点
        int currLevel = 0;          // 当前扩展节点所处的层序号
        int extendWeight = 0;         // 扩展节点所对应的载重量

        // 搜索子集空间树
        while (currLevel != N + 1) {
            // TODO 检查当前扩展结点的左儿子结点
            int wt = extendWeight + w[currLevel];
            if (wt <= c) {
                // 左儿子结点为可行节点
                addLiveNode(wt + remainArr[currLevel], currLevel + 1, e, true);
            }
            // TODO 检查右儿子结点
            addLiveNode(extendWeight + remainArr[currLevel], currLevel + 1, e, false);

            // 取下一扩展结点
            HeapNode node = heap.poll();
            currLevel = node.level;
            e = node.liveNode;
            extendWeight = node.uweight - remainArr[currLevel - 1];
        }
        // 构造当前最优解
        System.out.println("最优解数组为：");
        for (int i = 0; i <= N; i++) {
            best[i] = (e.leftChild) ? 0 : 1;
            if (i != N) {
                System.out.print(best[i] + " ");
            } else {
                System.out.println(best[i]);
            }
            e = e.parent;
        }
        return extendWeight;
    }

    /**
     * TODO 将活结点加入到表示活结点优先队列的最大堆中
     * @param up
     * @param lev
     * @param par
     * @param lChild
     */
    public static void addLiveNode(int up, int lev, BBnode par, boolean lChild) {
        BBnode b = new BBnode(par, lChild);
        HeapNode node = new HeapNode(b, up, lev);
        heap.add(node);
    }

    static class HeapNode implements Comparable {
        BBnode liveNode;        // 活结点
        int uweight;            // 活结点优先级
        int level;              //活结点在子集树种所处的层序号

        public HeapNode(BBnode node, int up, int lev) {
            liveNode = node;
            uweight = up;
            level = lev;
        }

        @Override
        public int compareTo(Object o) {
            int oUW = ((HeapNode) o).uweight;
            if (uweight < oUW) {
                return -1;
            }
            if (uweight == oUW) {
                return 0;
            }
            return 1;
        }

        @Override
        public boolean equals(Object obj) {
            return uweight == ((HeapNode) obj).uweight;
        }
    }

    static class BBnode {
        BBnode parent;
        boolean leftChild;

        public BBnode(BBnode par, boolean lchild) {
            parent = par;
            leftChild = lchild;
        }
    }
    
}