编辑代码

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

// 数据结构表示水果
typedef struct {
    char name[10];
    int weight;
    int value;
} Fruit;

// 比较函数，用于排序
int compare(const void *a, const void *b) {
    double ratioA = ((Fruit*)a)->value / (double)((Fruit*)a)->weight;
    double ratioB = ((Fruit*)b)->value / (double)((Fruit*)b)->weight;
    return (ratioB > ratioA) - (ratioB < ratioA);
}

// 贪心算法
void greedyKnapsack(Fruit fruits[], int n, int capacity) {
    qsort(fruits, n, sizeof(Fruit), compare);

    int currentWeight = 0;
    double totalValue = 0.0;

    for (int i = 0; i < n; i++) {
        if (currentWeight + fruits[i].weight <= capacity) {
            printf("装入%s，重量：%dkg，价值：%d元\n", fruits[i].name, fruits[i].weight, fruits[i].value);
            currentWeight += fruits[i].weight;
            totalValue += fruits[i].value;
        } else {
            double remainingCapacity = capacity - currentWeight;
            double fraction = remainingCapacity / fruits[i].weight;
            printf("装入%s（部分），重量：%dkg，价值：%.2f元\n", fruits[i].name, (int)remainingCapacity, fraction * fruits[i].value);
            totalValue += fraction * fruits[i].value;
            break;  // 背包已经装满
        }
    }

    printf("背包中装入水果的总价值为：%.2f元\n", totalValue);
}

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

    int n = sizeof(fruits) / sizeof(fruits[0]);
    int capacity = 20;

    printf("装水果的策略为：\n");
    greedyKnapsack(fruits, n, capacity);

    return 0;
}