编辑代码

#include <stdio.h>

#define N 4

// 物品结构体
struct Item {
    int weight;
    int value;
};

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

// 计算上界
int computeUpperBound(int remainingCapacity, int currentIndex, struct 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背包问题
void branchAndBoundKnapsack(int remainingCapacity, int currentValue, int currentIndex, struct Item items[], int totalItems, int currentSolution[]) {
    if (currentIndex == totalItems) {
        // 搜索到了叶子节点，更新最优解
        if (currentValue > globalBestValue) {
            globalBestValue = currentValue;
            for(int i=0; i<N; i++){
                globalBestSolution[i] = currentSolution[i];
            }
        }
        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;  // 回溯
    }
}

int main() {
    struct Item items[N] = {{3, 2}, {2, 5}, {4, 5}, {5, 8}};
    int capacity = 5;
    int currentSolution[N] = {0};

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

    printf("Global Best Value: %d\n", globalBestValue);
    printf("Global Best Solution: ");
    for (int i = 0; i < N; i++) {
        printf("%d ", globalBestSolution[i]);
    }
    printf("\n");

    return 0;
}