0-1背包问题分支限界法c语言实现

以下是0-1背包问题分支限界法的C语言实现示例：

#include <stdio.h>

#define MAX_N 100 // 背包中物品的最大数量

typedef struct {
    int weight; // 物品的重量
    int value; // 物品的价值
} Item;

int maxProfit = 0; // 最大价值
int bestSolution[MAX_N]; // 最优解
int currentSolution[MAX_N]; // 当前解
int currentWeight = 0; // 当前解的总重量
int currentValue = 0; // 当前解的总价值
int remainingValue = 0; // 剩余物品的总价值
Item items[MAX_N]; // 物品数组
int n; // 物品的数量
int capacity; // 背包的容量

// 计算剩余物品的总价值
int calculateRemainingValue(int k) {
    int remainingValue = 0;
    for (int i = k + 1; i < n; i++) {
        remainingValue += items[i].value;
    }
    return remainingValue;
}

// 回溯搜索
void backtrack(int k) {
    if (k == n) {
        if (currentValue > maxProfit) {
            maxProfit = currentValue;
            for (int i = 0; i < n; i++) {
                bestSolution[i] = currentSolution[i];
            }
        }
        return;
    }
    
    if (currentWeight + items[k].weight <= capacity) {
        currentWeight += items[k].weight;
        currentValue += items[k].value;
        remainingValue = calculateRemainingValue(k);
        
        if (currentValue + remainingValue > maxProfit) {
            currentSolution[k] = 1;
            backtrack(k + 1);
            currentSolution[k] = 0;
        }
        
        currentWeight -= items[k].weight;
        currentValue -= items[k].value;
    }
    
    if (currentValue + remainingValue > maxProfit) {
        currentSolution[k] = 0;
        backtrack(k + 1);
    }
}

int main() {
    printf("请输入物品的数量：");
    scanf("%d", &n);
    
    printf("请输入背包的容量：");
    scanf("%d", &capacity);
    
    printf("请输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &items[i].weight, &items[i].value);
    }
    
    backtrack(0);
    
    printf("最大价值为：%d\n", maxProfit);
    printf("最优解为：");
    for (int i = 0; i < n; i++) {
        printf("%d ", bestSolution[i]);
    }
    printf("\n");
    
    return 0;
}