java分支限界法求01背包问题

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

import java.util.Arrays;

public class KnapsackProblem {
    private static int maxProfit = Integer.MIN_VALUE;
    private static int[] bestSolution;

    public static void branchAndBound(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] currentSolution = new int[n];
        int currentWeight = 0;
        int currentValue = 0;
        int currentIndex = 0;

        branch(0, weights, values, capacity, currentSolution, currentWeight, currentValue, currentIndex);

        System.out.println("Best solution: " + Arrays.toString(bestSolution));
        System.out.println("Max profit: " + maxProfit);
    }

    private static void branch(int level, int[] weights, int[] values, int capacity, int[] currentSolution, int currentWeight, int currentValue, int currentIndex) {
        if (level == weights.length) {
            if (currentValue > maxProfit) {
                maxProfit = currentValue;
                bestSolution = currentSolution.clone();
            }
            return;
        }

        if (currentWeight + weights[level] <= capacity) {
            currentSolution[level] = 1;
            branch(level + 1, weights, values, capacity, currentSolution, currentWeight + weights[level], currentValue + values[level], currentIndex + 1);
        }

        currentSolution[level] = 0;
        branch(level + 1, weights, values, capacity, currentSolution, currentWeight, currentValue, currentIndex + 1);
    }

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

        branchAndBound(weights, values, capacity);
    }
}