编辑代码

#include <stdio.h>

#define MAX_N 100

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

int maxProfit;  // 最大总价值
int bestSolution[MAX_N];  // 最佳解决方案
int currentSolution[MAX_N];  // 当前解决方案

// 计算剩余物品的上界（使用贪心法）
int bound(Item items[], int n, int capacity, int level, int weight, int value) {
    int boundValue = value;
    int totalWeight = weight;
    
    // 将物品按单位重量价值从大到小排序
    for (int i = level; i < n; i++) {
        if (totalWeight + items[i].weight <= capacity) {
            totalWeight += items[i].weight;
            boundValue += items[i].value;
        } else {
            boundValue += (capacity - totalWeight) * items[i].value / items[i].weight;
            break;
        }
    }
    
    return boundValue;
}

// 使用分支界限法求解背包问题
void knapsack(Item items[], int n, int capacity, int level, int weight, int value) {
    // 到达叶子节点时更新最大总价值和最佳解决方案
    if (level == n) {
        if (value > maxProfit) {
            maxProfit = value;
            for (int i = 0; i < n; i++) {
                bestSolution[i] = currentSolution[i];
            }
        }
        return;
    }
    
    // 计算当前节点的上界
    int upperBound = bound(items, n, capacity, level, weight, value);
    
    // 如果上界小于等于当前最大总价值，则剪枝
    if (upperBound <= maxProfit) {
        return;
    }
    
    // 不选择当前物品
    knapsack(items, n, capacity, level + 1, weight, value);
    
    // 选择当前物品
    if (weight + items[level].weight <= capacity) {
        currentSolution[level] = 1;
        knapsack(items, n, capacity, level + 1, weight + items[level].weight, value + items[level].value);
        currentSolution[level] = 0;
    }
}

int main() {
    int n;  // 物品数量
    int capacity;  // 背包容量
    Item items[MAX_N];  // 物品数组
    
    // 输入物品数量和背包容量
    printf("请输入物品数量：");
    scanf("%d", &n);
    printf("请输入背包容量：");
    scanf("%d", &capacity);
    
    // 输入每个物品的重量和价值
    printf("请依次输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        printf("物品 %d：", i + 1);
        scanf("%d%d", &items[i].weight, &items[i].value);
    }
    
    maxProfit = 0;
    
    // 使用分支界限法求解背包问题
    knapsack(items, n, capacity, 0, 0, 0);
    
    // 输出最大总价值和最佳解决方案
    printf("最大总价值：%d\n", maxProfit);
    printf("最佳解决方案：");
    for (int i = 0; i < n; i++) {
        printf("%d ", bestSolution[i]);
    }
    printf("\n");
    
    return 0;
}