编辑代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 4;

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

    Item(int w, int v) : weight(w), value(v) {}
};

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

// 计算上界
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背包问题
void branchAndBoundKnapsack(int remainingCapacity, int currentValue, int currentIndex, Item items[], int totalItems, int currentSolution[]) {
    if (currentIndex == totalItems) {
        // 搜索到了叶子节点，更新最优解
        if (currentValue > globalBestValue) {
            globalBestValue = currentValue;
            copy(currentSolution, currentSolution + totalItems, globalBestSolution);
        }
        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() {
    Item items[] = {Item(3, 2), Item(2, 5), Item(4, 5), Item(5, 8)};
    int capacity = 5;
    int currentSolution[N];
    branchAndBoundKnapsack(capacity, 0, 0, items, N, currentSolution);
    cout << "Global Best Value: " << globalBestValue << endl;
    cout << "Global Best Solution: ";
    for (int i = 0; i < N; i++) {
        cout << globalBestSolution[i] << " ";
    }
    cout << endl;
    return 0;
}