编辑代码

#include <stdio.h>

// 定义水果结构体
typedef struct {
    char *name; // 水果名称
    double weight; // 重量
    double value; // 价值
    double ratio; // 单位价值
} Fruit;

// 比较函数，按照单位价值从大到小排序
int compare(const void *a, const void *b) {
    Fruit *fruit1 = (Fruit *)a;
    Fruit *fruit2 = (Fruit *)b;
    if (fruit1->ratio < fruit2->ratio) return 1;
    if (fruit1->ratio > fruit2->ratio) return -1;
    return 0;
}

// 分数背包问题的贪心算法实现
void fractionalKnapsack(Fruit fruits[], int n, double capacity) {
    // 按照单位价值从大到小排序
    qsort(fruits, n, sizeof(Fruit), compare);

    double totalValue = 0; // 背包中水果的总价值
    for (int i = 0; i < n; i++) {
        if (fruits[i].weight <= capacity) {
            // 如果当前水果可以完全装入背包
            capacity -= fruits[i].weight;
            totalValue += fruits[i].value;
            printf("装入全部%s: %.2fkg, 价值: %.2f元\n", fruits[i].name, fruits[i].weight, fruits[i].value);
        } else {
            // 如果当前水果只能装入部分
            totalValue += fruits[i].ratio * capacity;
            printf("装入部分%s: %.2fkg, 价值: %.2f元\n", fruits[i].name, capacity, fruits[i].ratio * capacity);
            break; // 背包已满，结束循环
        }
    }
    printf("背包中装入水果的总价值: %.2f元\n", totalValue);
}

int main() {
    // 初始化水果数组
    Fruit fruits[] = {
        {"苹果", 15, 300, 20},
        {"香蕉", 18, 180, 10},
        {"橘子", 10, 150, 15},
        {"猕猴桃", 9, 270, 30}
    };
    int n = 4;
    double capacity = 20; // 背包承重

    // 计算每种水果的单位价值
    for (int i = 0; i < n; i++) {
        fruits[i].ratio = fruits[i].value / fruits[i].weight;
    }

    // 调用分数背包问题的贪心算法
    fractionalKnapsack(fruits, n, capacity);

    return 0;
}