0-1背包问题-分支限界法(优先队列分支限界法)Java代码

以下是0-1背包问题-分支限界法(优先队列分支限界法)Java代码的实现：

首先需要定义一个Item类，用来存储每一个物品的价值和重量：

class Item {
    int value;
    int weight;
    double ratio;
    Item(int value, int weight) {
        this.value = value;
        this.weight = weight;
        this.ratio = (double) value / weight;
    }
}

然后需要实现一个比较器，用来将Item按照价值重量比从大到小排序：

class ItemComparator implements Comparator<Item> {
    public int compare(Item a, Item b) {
        if (b.ratio > a.ratio) {
            return 1;
        } else if (b.ratio < a.ratio) {
            return -1;
        } else {
            return 0;
        }
    }
}

接下来就是主要的解法实现，使用优先队列进行分支限界法：

class Solution {
    public int knapsack(int[] values, int[] weights, int maxWeight) {
        int n = values.length;
        Item[] items = new Item[n];
        for (int i = 0; i < n; i++) {
            items[i] = new Item(values[i], weights[i]);
        }
        Arrays.sort(items, new ItemComparator()); //按照价值重量比从大到小排序
        
        PriorityQueue<Node> queue = new PriorityQueue<>(new NodeComparator()); //用优先队列保存每个节点
        queue.offer(new Node(0, 0, 0));
        
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.level == n) { //已经处理完所有物品
                return cur.value;
            }
            int weight = cur.weight, value = cur.value, level = cur.level;
            Item item = items[level];
            //计算上界
            double bound = value + (double) (maxWeight - weight) * item.ratio; 
            if (bound <= maxWeight) { //上界小于最大重量，放入全部物品
                queue.offer(new Node(value + item.value, weight + item.weight, level + 1));
            } else { //上界大于等于最大重量，只放入一部分物品
                queue.offer(new Node(value + (int) (item.ratio * (maxWeight - weight)), maxWeight, level + 1)); //放入剩余空间能放下的那部分物品
            }
            queue.offer(new Node(value, weight, level + 1)); //不放入这个物品
        }
        return 0; //无解
    }
}

class Node {
    int value;
    int weight;
    int level;
    Node(int value, int weight, int level) {
        this.value = value;
        this.weight = weight;
        this.level = level;
    }
}

class NodeComparator implements Comparator<Node> {
    public int compare(Node a, Node b) {
        return b.value - a.value; //按照价值从大到小排序
    }
}

在任何时候，这个解法都只会处理少量的节点，因此时间复杂度为O(nlogn)。（其中n为物品数量）