编辑代码

#include <stdio.h>

typedef struct {
    int weight;
    int value;
} Item;

int max_value = 0;  // 当前已知的最优解

void branchAndBound(int capacity, Item items[], int current_weight, int current_value, int index) {
    if (index < 0) {
        if (current_value > max_value) {
            max_value = current_value;
        }
        return;
    }

    // 计算当前节点的上界
    int upper_bound = current_value;
    int remaining_capacity = capacity - current_weight;
    int i = index;
    while (i >= 0 && remaining_capacity >= items[i].weight) {
        upper_bound += items[i].value;
        remaining_capacity -= items[i].weight;
        i--;
    }

    // 剪枝操作
    if (upper_bound <= max_value) {
        return;
    }

    // 选择当前物品
    if (current_weight + items[index].weight <= capacity) {
        branchAndBound(capacity, items, current_weight + items[index].weight, current_value + items[index].value, index - 1);
    }

    // 不选择当前物品
    branchAndBound(capacity, items, current_weight, current_value, index - 1);
}

int main() {
    int capacity = 4;

    Item items[3];
    items[0].weight = 4;
    items[0].value = 3000;
    items[1].weight = 3;
    items[1].value = 2000;
    items[2].weight = 1;
    items[2].value = 1500;

    branchAndBound(capacity, items, 0, 0, 2);

    printf("The maximum value is: %d\n", max_value);

    return 0;
}