编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 物品结构体
typedef struct {
    char name[20]; // 物品名称
    int weight; // 物品重量
    int value; // 物品价值
} Item;

// 使用暴力穷举法解决背包问题
int Bag(int count, int capacity, Item* items) {
    int maxWeight = 0; // 当前最大重量
    int maxValue = 0; // 当前最大价值
    int maxCombination = 0; // 当前最大组合在二进制中的表示
    int i , j ;

    // 根据物品数量，遍历所有可能的组合情况
    for (i = 0; i < (1 << count); ++i) {//表示将数字1左移count位，实际上就是计算出了从0到count-1的二进制数所能表示的最大值加1。
        
        int currentWeight = 0; // 当前组合的总重量
        int currentValue = 0; // 当前组合的总价值

        // 计算当前组合的总重量和总价值
        for (j = 0; j < count; ++j) {
            if ((i >> j) & 1) { // 判断物品是否被选中
                currentWeight += items[j].weight;
                currentValue += items[j].value;
            }
        }

        // 如果当前组合的总重量小于等于背包容量，并且总价值大于先前的最大价值
        if (currentWeight <= capacity && currentValue > maxValue) {
            maxWeight = currentWeight;
            maxValue = currentValue;
            maxCombination = i;
        }
    }

    // 输出选择的水果
    printf("菜篮子：");
    for (i = 0; i < count; ++i) {
        if ((maxCombination >> i) & 1) {
            printf("%s ", items[i].name);
        }
    }
    printf("\n");

    return maxValue;
}

int main() {
    int count = 5; // 水果数量
    int capacity = 10; // 菜篮子容量

    // 初始化物品数组
    Item items[5];
    strcpy(items[0].name, "苹果");
    items[0].weight = 2;
    items[0].value = 3;

    strcpy(items[1].name, "香梨");
    items[1].weight = 3;
    items[1].value = 4;

    strcpy(items[2].name, "橘子");
    items[2].weight = 4;
    items[2].value = 5;

    strcpy(items[3].name, "西瓜");
    items[3].weight = 5;
    items[3].value = 8;

    strcpy(items[4].name, "草莓");
    items[4].weight = 9;
    items[4].value = 10;

    int maxValue = Bag(count, capacity, items);

    printf("一共：%d元\n", maxValue);

    return 0;
}