编辑代码

public class KnapsackBranchAndBound {

    private static final int N = 4;

    // 物品结构体
    static class Item {
        int weight;
        int value;

        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }
    }

    // 全局变量，用于记录最优解
    private static int globalBestValue = 0;
    private static int[] globalBestSolution = new int[N];

    public static void main(String[] args) {
        Item[] items = {new Item(3, 2), new Item(2, 5), new Item(4, 5), new Item(5, 8)};
        int capacity = 5;
        int[] currentSolution = new int[N];

        branchAndBoundKnapsack(capacity, 0, 0, items, N, currentSolution);

        System.out.println("Global Best Value: " + globalBestValue);
        System.out.print("Global Best Solution: ");
        for (int i = 0; i < N; i++) {
            System.out.print(globalBestSolution[i] + " ");
        }
        System.out.println();
    }

    // 计算上界
    private static int computeUpperBound(int remainingCapacity, int currentIndex, Item[] items, int totalItems) {
        int upperBound = 0;

        for (int i = currentIndex; i < totalItems; i++) {
            if (items[i].weight <= remainingCapacity) {
                upperBound += items[i].value;
                remainingCapacity -= items[i].weight;
            } else {
                // Include a fraction of the next item to fill the remaining capacity
                upperBound += (remainingCapacity * items[i].value) / items[i].weight;
                break;
            }
        }

        return upperBound;
    }

    // 分支界限法解决0/1背包问题
    private static void branchAndBoundKnapsack(int remainingCapacity, int currentValue, int currentIndex, Item[] items, int totalItems, int[] currentSolution) {
        if (currentIndex == totalItems) {
            // 搜索到了叶子节点，更新最优解
            if (currentValue > globalBestValue) {
                globalBestValue = currentValue;
                System.arraycopy(currentSolution, 0, globalBestSolution, 0, totalItems);
            }
            return;
        }

        // Case 1: Include the current item
        if (items[currentIndex].weight <= remainingCapacity) {
            int newRemainingCapacity = remainingCapacity - items[currentIndex].weight;
            int newValue = currentValue + items[currentIndex].value;

            // 计算上界
            int upperBound = computeUpperBound(newRemainingCapacity, currentIndex + 1, items, totalItems);

            if (upperBound > globalBestValue) {
                // 在当前分支上搜索
                currentSolution[currentIndex] = 1;
                branchAndBoundKnapsack(newRemainingCapacity, newValue, currentIndex + 1, items, totalItems, currentSolution);
                currentSolution[currentIndex] = 0;  // 回溯
            }
        }

        // Case 2: Exclude the current item
        int upperBound = computeUpperBound(remainingCapacity, currentIndex + 1, items, totalItems);
        if (upperBound > globalBestValue) {
            // 在当前分支上搜索
            currentSolution[currentIndex] = 0;
            branchAndBoundKnapsack(remainingCapacity, currentValue, currentIndex + 1, items, totalItems, currentSolution);
            currentSolution[currentIndex] = 1;  // 回溯
        }
    }
}