编辑代码

#include <stdio.h>

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

// 定义全局变量表示最优解
int maxProfit = 0;

// 检查是否可以加入背包
int isFeasible(int weight, int value, int capacity) {
    return (weight <= capacity);
}

// 计算上界（启发函数）
float upperBound(int level, int profit, int weight, int capacity, struct Item items[], int n) {
    float upperBound = profit;
    int totalWeight = weight;

    // 从当前层开始，尽量加入价值最高的物品
    for (int i = level; i < n; i++) {
        if (totalWeight + items[i].weight <= capacity) {
            totalWeight += items[i].weight;
            upperBound += items[i].value;
        } else {
            // 加入部分物品
            int remainingCapacity = capacity - totalWeight;
            upperBound += (float)items[i].value * remainingCapacity / items[i].weight;
            break;
        }
    }

    return upperBound;
}

// 分支界限法求解背包问题
void knapsack(int level, int profit, int weight, int capacity, struct Item items[], int n) {
    // 检查是否达到叶子节点
    if (level == n) {
        if (profit > maxProfit) {
            maxProfit = profit;
        }
        return;
    }

    // 检查左子树（不选择当前物品）
    knapsack(level + 1, profit, weight, capacity, items, n);

    // 检查右子树（选择当前物品）
    if (isFeasible(weight + items[level].weight, profit + items[level].value, capacity)) {
        knapsack(level + 1, profit + items[level].value, weight + items[level].weight, capacity, items, n);
    }
}

int main() {
    // 背包容量和物品列表
    int capacity = 10;
    struct Item items[] = {{2, 10}, {3, 5}, {5, 15}, {7, 7}, {1, 6}};

    // 物品数量
    int n = sizeof(items) / sizeof(items[0]);

    // 调用分支界限法
    knapsack(0, 0, 0, capacity, items, n);

    // 输出最优解
    printf("Maximum Profit: %d\n", maxProfit);

    return 0;
}