n=5, C1 =120,C2 =80, w= {60,40,10,30,50} 。采用优先队列式分支限界算法解决该问题。 java

以下是Java实现代码：

import java.util.*;

public class KnapsackProblem {
    static int n = 5;
    static int C1 = 120;
    static int C2 = 80;
    static int[] w = {60, 40, 10, 30, 50};
    static int[] v = {10, 40, 30, 50, 35};

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

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

        public int compareTo(Node other) {
            return other.bound - this.bound;
        }
    }

    public static int knapsack() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int maxProfit = 0;
        Node u = new Node(-1, 0, 0, bound(-1, 0, 0));
        pq.offer(u);
        while (!pq.isEmpty()) {
            u = pq.poll();
            if (u.bound > maxProfit) {
                Node v1 = new Node(u.level + 1, u.profit + v[u.level + 1], u.weight + w[u.level + 1], bound(u.level + 1, u.profit + v[u.level + 1], u.weight + w[u.level + 1]));
                Node v2 = new Node(u.level + 1, u.profit, u.weight, bound(u.level + 1, u.profit, u.weight));
                if (v1.weight <= C1 && v1.profit > maxProfit)
                    maxProfit = v1.profit;
                if (v1.bound > maxProfit)
                    pq.offer(v1);
                if (v2.bound > maxProfit)
                    pq.offer(v2);
            }
        }
        return maxProfit;
    }

    public static int bound(int level, int profit, int weight) {
        if (weight > C1)
            return 0;
        int bound = profit;
        int j = level + 1;
        int totWeight = weight;
        while (j < n && totWeight + w[j] <= C2) {
            totWeight += w[j];
            bound += v[j];
            j++;
        }
        if (j < n)
            bound += (C2 - totWeight) * v[j] / w[j];
        return bound;
    }

    public static void main(String[] args) {
        int maxProfit = knapsack();
        System.out.println("The maximum profit is: " + maxProfit);
    }
}

其中，`Node`类表示分支限界树中的节点，包含`level`表示当前节点的层数，`profit`表示当前已选物品的总价值，`weight`表示当前已选物品的总重量，`bound`表示当前节点的上界。

`knapsack()`方法使用优先队列式分支限界算法求解该问题。首先，将根节点加入优先队列，然后不断从队列中取出上界最大的节点进行扩展，直到队列为空或者上界小于当前已知的最大利润。每次扩展节点时，分别考虑选取当前物品和不选取当前物品两种情况，计算扩展后的节点的上界，并将可行的节点加入队列中。

`bound()`方法用于计算当前节点的上界。对于已经选取的物品，直接将它们的价值相加。对于未选取的物品，采用贪心策略计算其价值的上限，即先按单位重量价值排序，然后依次选取物品，直到达到背包的容量限制或者所有物品都被选取。