编辑代码

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

// 结构体表示豆子的属性
struct Bean {
    int weight;
    int value;
    double unitValue; // 单位价值
};
// 按单位价值从高到低排序
int compareUnitValue(const void *a, const void *b) {
    return ((struct Bean *)b)->unitValue - ((struct Bean *)a)->unitValue;
}
// 贪心算法解决豆子背包问题
double greedyBeanKnapsack(struct Bean *beans, int n, int capacity) {
    // 计算单位价值
    for (int i = 0; i < n; ++i) {
        beans[i].unitValue = (double)beans[i].value / beans[i].weight;
    }
    // 按单位价值排序
    qsort(beans, n, sizeof(struct Bean), compareUnitValue);
    // 贪心选择
    double totalValue = 0.0;
    int currentWeight = 0;

    for (int i = 0; i < n && currentWeight < capacity; ++i) {
        int selectedWeight = (beans[i].weight < capacity - currentWeight) ? beans[i].weight : capacity - currentWeight;
        totalValue += selectedWeight * beans[i].unitValue;
        currentWeight += selectedWeight;
    }

    return totalValue;
}

int main() {
    // 示例：三颗豆子的重量和价值
    struct Bean beans[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(beans) / sizeof(beans[0]);
    int capacity = 50;

    double maxValue = greedyBeanKnapsack(beans, n, capacity);

    printf("Maximum value that can be obtained = %.2lf\n", maxValue);

    return 0;
}