编辑代码

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

// 定义水果结构体
struct Fruit {
    char name[10];
    int weight;
    int value;
};

// 比较函数,用于qsort排序
int compare(const void *a, const void *b) {
    int ratioA = ((struct Fruit*)a)->value / ((struct Fruit*)a)->weight;
    int ratioB = ((struct Fruit*)b)->value / ((struct Fruit*)b)->weight;
    return ratioB - ratioA;  // 按照单位价值降序排序
}

// 贪心算法函数,返回最大总价值
int greedyKnapsack(struct Fruit fruits[], int n, int capacity) {
    // 按单位价值降序排序
    qsort(fruits, n, sizeof(struct Fruit), compare);

    int totalValue = 0; // 总价值
    int currentWeight = 0; // 当前背包中的总重量

    // 依次选择单位价值最高的水果放入背包
    for (int i = 0; i < n; ++i) {
        if (currentWeight + fruits[i].weight <= capacity) {
            // 当前水果可以完整放入背包
            currentWeight += fruits[i].weight;
            totalValue += fruits[i].value;
            printf("%s(%dkg),", fruits[i].name, fruits[i].weight);
        } else {
            // 当前水果无法完整放入背包,只放入一部分
            int remainingWeight = capacity - currentWeight;
            int fraction = (remainingWeight * fruits[i].value) / fruits[i].weight;
            totalValue += fraction;
            printf("%s(%dkg部分),", fruits[i].name, remainingWeight);
            break; // 背包已满,退出循环
        }
    }

    return totalValue;
}

int main() {
    // 定义水果数组
    struct Fruit fruits[] = {
        {"苹果", 15, 300},
        {"香蕉", 18, 180},
        {"橘子", 10, 150},
        {"猕猴桃", 9, 270}
    };

    int n = sizeof(fruits) / sizeof(fruits[0]); // 水果数量
    int capacity = 20; // 背包承重

    // 调用贪心算法函数
    int maxTotalValue = greedyKnapsack(fruits, n, capacity);

    // 输出结果
    printf("\n背包中水果的总价值为:%d 元\n", maxTotalValue);

    return 0;
}