01背包分支界限法java

下面是01背包问题的分支界限法的Java实现：

import java.util.PriorityQueue;

class Node implements Comparable<Node>{
    int level;
    int profit;
    int weight;
    double bound;
    Node parent;

    public Node(int level, int profit, int weight, double bound, Node parent){
        this.level = level;
        this.profit = profit;
        this.weight = weight;
        this.bound = bound;
        this.parent = parent;
    }

    public int compareTo(Node node){
        return Double.compare(node.bound, this.bound);
    }
}

public class BranchAndBound {
    static int n = 4;  // 物品数量
    static int[] w = {2, 3, 4, 5};  // 物品重量
    static int[] p = {3, 4, 5, 6};  // 物品价值
    static int c = 8;  // 背包容量

    public static void main(String[] args) {
        PriorityQueue<Node> queue = new PriorityQueue<Node>();
        Node u = new Node(-1, 0, 0, bound(-1, 0, 0), null);
        queue.offer(u);
        int maxValue = 0;

        while (!queue.isEmpty()){
            Node node = queue.poll();
            if (node.bound > maxValue && node.level < n - 1){
                Node left = new Node(node.level + 1, node.profit + p[node.level + 1], node.weight + w[node.level + 1], bound(node.level + 1, node.profit + p[node.level + 1], node.weight + w[node.level + 1]), node);
                if (left.weight <= c && left.profit > maxValue) maxValue = left.profit;
                queue.offer(left);

                Node right = new Node(node.level + 1, node.profit, node.weight, bound(node.level + 1, node.profit, node.weight), node);
                if (right.bound > maxValue) queue.offer(right);
            }
        }

        System.out.println("最大价值是：" + maxValue);
    }

    public static double bound(int i, int profit, int weight){
        if (weight > c) return 0;
        double bound = profit;
        int j = i + 1;
        int totalWeight = weight;
        while (j < n && totalWeight + w[j] <= c){
            totalWeight += w[j];
            bound += p[j];
            j++;
        }
        if (j < n) bound += (c - totalWeight) * (p[j] * 1.0 / w[j]);
        return bound;
    }
}

这个实现中，我们使用了一个优先队列来维护所有的节点，并按照上界从大到小的顺序进行搜索。在搜索过程中，我们首先取出上界最大的节点，然后分别计算选择该节点的左右儿子节点，将这两个节点加入队列中。在计算左右儿子节点的上界时，我们使用了贪心策略，即尽量选择价值最高的物品。