编辑代码

#include <stdio.h>
#include <stdbool.h>

// 商品结构体
struct Item {
    char name[20];
    int value;
    int weight;
};

// 计算商品的单位价值
float calculateUnitValue(struct Item item) {
    return (float)item.value / item.weight;
}

// 根据单位价值排序商品
void sortByUnitValue(struct Item items[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (calculateUnitValue(items[j]) < calculateUnitValue(items[j + 1])) {
                // 交换两个商品
                struct Item temp = items[j];
                items[j] = items[j + 1];
                items[j + 1] = temp;
            }
        }
    }
}

// 贪心算法求解背包问题
void knapsack(struct Item items[], int n, int capacity) {
    sortByUnitValue(items, n);

    int currentWeight = 0;
    float totalValue = 0.0;

    for (int i = 0; i < n; i++) {
        if (currentWeight + items[i].weight <= capacity) {
            // 将商品放入背包
            currentWeight += items[i].weight;
            totalValue += items[i].value;
            printf("偷取 %s，价值: %d 美元，重量: %d\n", items[i].name, items[i].value, items[i].weight);
        }
    }

    printf("总价值：%0.2f 美元\n", totalValue);
}

int main() {
    struct Item items[] = {
        {"音响", 3000, 4},
        {"笔记本电脑", 2000, 3},
        {"吉他", 1500, 1}
    };

    int n = sizeof(items) / sizeof(items[0]);
    int capacity = 4;

    printf("背包容量：%d\n", capacity);
    knapsack(items, n, capacity);

    return 0;
}