优先队列式分支界限法解决装载问题的java代码

以下是使用优先队列式分支界限法解决装载问题的Java代码示例：

import java.util.*;

public class Knapsack {
    private static int[] w; // 物品重量
    private static int[] v; // 物品价值
    private static int c; // 背包容量
    private static int n; // 物品数量
    private static int maxValue = 0; // 最大价值
    private static PriorityQueue<Node> queue = new PriorityQueue<>(); // 优先队列

    // 节点类
    private static class Node implements Comparable<Node> {
        int level; // 层数
        int weight; // 当前重量
        int value; // 当前价值
        double bound; // 上界

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

        // 按照上界从大到小排序
        public int compareTo(Node o) {
            return Double.compare(o.bound, this.bound);
        }
    }

    // 计算上界
    private static double bound(int level, int weight, int value) {
        double bound = value;
        int j = level + 1;
        int totalWeight = weight;
        while (j < n && totalWeight + w[j] <= c) {
            totalWeight += w[j];
            bound += v[j];
            j++;
        }
        if (j < n) {
            bound += (c - totalWeight) * (v[j] * 1.0 / w[j]); // 装满背包
        }
        return bound;
    }

    // 优先队列式分支界限法
    private static void knapsack() {
        Node u = new Node(-1, 0, 0, bound(-1, 0, 0)); // 根节点
        queue.offer(u);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.bound > maxValue) { // 当前上界大于最大价值才继续搜索
                if (node.level == n - 1) { // 叶子节点
                    if (node.value > maxValue) {
                        maxValue = node.value;
                    }
                } else {
                    // 左节点：选当前物品
                    int weightLeft = node.weight + w[node.level + 1];
                    int valueLeft = node.value + v[node.level + 1];
                    double boundLeft = bound(node.level + 1, weightLeft, valueLeft);
                    if (boundLeft > maxValue) { // 当前上界大于最大价值才加入优先队列
                        queue.offer(new Node(node.level + 1, weightLeft, valueLeft, boundLeft));
                    }

                    // 右节点：不选当前物品
                    int weightRight = node.weight;
                    int valueRight = node.value;
                    double boundRight = bound(node.level + 1, weightRight, valueRight);
                    if (boundRight > maxValue) { // 当前上界大于最大价值才加入优先队列
                        queue.offer(new Node(node.level + 1, weightRight, valueRight, boundRight));
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("请输入背包容量：");
        c = in.nextInt();
        System.out.print("请输入物品数量：");
        n = in.nextInt();
        w = new int[n];
        v = new int[n];
        System.out.println("请输入每个物品的重量和价值：");
        for (int i = 0; i < n; i++) {
            w[i] = in.nextInt();
            v[i] = in.nextInt();
        }
        knapsack();
        System.out.println("最大价值为：" + maxValue);
    }
}

在上面的代码中，我们使用了一个优先队列来存储节点，并按照节点的上界从大到小排序。在搜索过程中，每次取出优先队列中上界最大的节点进行扩展。当当前节点的上界小于等于最大价值时，就不再扩展该节点。每次扩展时，我们分别考虑选当前物品和不选当前物品两种情况，分别计算出左右子节点的上界，并将它们加入优先队列中。当优先队列为空时，搜索结束，最大价值就是我们要求的结果。

注意，我们在计算上界时，采用了贪心策略，即优先选择单位重量价值最大的物品装入背包，直到装满为止。如果当前物品不能完全装入背包，则将其按照比例装入背包。这样可以保证计算出的上界是一个比较准确的估计值。