0/1背包问题的分支限界算法的java代码

以下是0/1背包问题的分支限界算法的Java代码：

import java.util.*;

public class KnapsackProblem {

    private static class Item {
        int weight;
        int value;
        double density;

        public Item(int w, int v) {
            weight = w;
            value = v;
            density = (double) v / (double) w;
        }
    }

    private static class Node {
        int level;
        int weight;
        int value;
        double bound;

        public Node(int l, int w, int v, double b) {
            level = l;
            weight = w;
            value = v;
            bound = b;
        }
    }

    public static int knapsack(int W, int[] weights, int[] values, int n) {
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(weights[i], values[i]);
        }
        Arrays.sort(items, (a, b) -> Double.compare(b.density, a.density));
        Queue<Node> queue = new PriorityQueue<>((a, b) -> Double.compare(b.bound, a.bound));
        Node root = new Node(-1, 0, 0, bound(items, W, -1, 0, 0));
        queue.offer(root);
        int maxProfit = 0;
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.bound > maxProfit) {
                if (node.level == n - 1) {
                    maxProfit = node.value;
                } else {
                    int level = node.level + 1;
                    int weight = node.weight + items[level].weight;
                    int value = node.value + items[level].value;
                    if (weight <= W && value > maxProfit) {
                        maxProfit = value;
                    }
                    double bound = bound(items, W, level, weight, value);
                    if (bound > maxProfit) {
                        queue.offer(new Node(level, weight, value, bound));
                    }
                    queue.offer(new Node(level, node.weight, node.value, bound));
                }
            }
        }
        return maxProfit;
    }

    private static double bound(Item[] items, int W, int level, int weight, int value) {
        double bound = value;
        int i = level + 1;
        int remainingWeight = W - weight;
        while (i < items.length && remainingWeight > 0) {
            if (items[i].weight <= remainingWeight) {
                bound += items[i].value;
                remainingWeight -= items[i].weight;
            } else {
                bound += items[i].density * remainingWeight;
                remainingWeight = 0;
            }
            i++;
        }
        return bound;
    }

    public static void main(String[] args) {
        int W = 50;
        int[] weights = {10, 20, 30};
        int[] values = {60, 100, 120};
        int n = weights.length;
        int maxProfit = knapsack(W, weights, values, n);
        System.out.println("Max profit: " + maxProfit);
    }
}

其中，`Item`类表示物品，包含物品的重量、价值和单位重量价值；`Node`类表示搜索树的节点，包含节点的层数、已选物品的重量、价值和上界；`knapsack`方法是求解0/1背包问题的分支限界算法的主函数；`bound`方法是计算节点的上界。在`knapsack`方法中，首先将物品按单位重量价值从大到小排序；然后创建一个优先队列，将根节点入队；接着不断从队列中取出节点，如果该节点的上界比当前最大价值还要大，则扩展该节点，计算其左右儿子节点的上界，并将其入队。最终返回最大价值。在`bound`方法中，先计算已选物品的价值，然后从当前层的下一层开始，按单位重量价值从大到小选择物品，直到不能继续放入为止。