编辑代码

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


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


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

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

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

    // 依次选择单位价值最高的水果放入背包
    for (int i = 0; i < n; ++i) {
        int remainingweights = capacity - currentweights;

        if (remainingweights > 0 && fruits[i].weights <= remainingweights) {
            // 当前水果可以完整放入背包
            currentweights += fruits[i].weights;
            totalprice += fruits[i].price;
            printf("%s（%dkg），", fruits[i].name, fruits[i].weights);
        } else if (remainingweights > 0) {
            // 当前水果无法完整放入背包，只放入一部分
            int fraction = (remainingweights * fruits[i].price) / fruits[i].weights;
            totalprice += fraction;
            printf("%s（%dkg部分），", fruits[i].name, remainingweights);
            break; // 背包已满，退出循环
        }
    }

    return totalprice;
}

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

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

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

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

    return 0;
}