分支限界法求解01背包java

以下是使用分支限界法求解01背包问题的Java代码示例：

import java.util.PriorityQueue;

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

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

    public int compareTo(Node other) {
        if (this.bound > other.bound) {
            return -1;
        } else if (this.bound < other.bound) {
            return 1;
        } else {
            return 0;
        }
    }
}

public class Knapsack {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int maxProfit = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        Node u = new Node(-1, 0, 0, 0);
        Node v;

        u.bound = computeBound(u, weights, values, capacity, n);
        pq.add(u);

        while (!pq.isEmpty()) {
            u = pq.poll();

            if (u.bound > maxProfit) {
                v = new Node(0, 0, 0, 0);

                if (u.level == -1) {
                    v.level = 0;
                } else if (u.level != n - 1) {
                    v.level = u.level + 1;
                }

                v.weight = u.weight + weights[v.level];
                v.profit = u.profit + values[v.level];

                if (v.weight <= capacity && v.profit > maxProfit) {
                    maxProfit = v.profit;
                }

                v.bound = computeBound(v, weights, values, capacity, n);

                if (v.bound > maxProfit) {
                    pq.add(v);
                }

                v = new Node(0, 0, 0, 0);
                v.weight = u.weight;
                v.profit = u.profit;

                v.bound = computeBound(v, weights, values, capacity, n);

                if (v.bound > maxProfit) {
                    pq.add(v);
                }
            }
        }

        return maxProfit;
    }

    private static double computeBound(Node u, int[] weights, int[] values, int capacity, int n) {
        int j, k;
        int totalWeight;
        double result;

        if (u.weight >= capacity) {
            return 0;
        } else {
            result = u.profit;
            j = u.level + 1;
            totalWeight = u.weight;

            while (j < n && totalWeight + weights[j] <= capacity) {
                totalWeight += weights[j];
                result += values[j];
                j++;
            }

            k = j;

            if (k < n) {
                result += (capacity - totalWeight) * (values[k] / (double) weights[k]);
            }

            return result;
        }
    }

    public static void main(String[] args) {
        int[] weights = {12, 3, 11, 5, 6, 8, 9, 4, 7, 10};
        int[] values = {6, 2, 7, 3, 2, 9, 8, 10, 4, 5};
        int capacity = 50;

        int maxProfit = knapsack(weights, values, capacity);
        System.out.println("Maximum profit: " + maxProfit);
    }
}