编辑代码

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

// 豆子结构体
typedef struct {
    int value; // 价值
    int weight; // 重量
    double ratio; // 单位重量价值
} Bean;

// 比较函数，用于排序
int compare(const void *a, const void *b) {
    Bean *beanA = (Bean *)a;
    Bean *beanB = (Bean *)b;
    if(beanA->ratio < beanB->ratio) return 1;
    if(beanA->ratio > beanB->ratio) return -1;
    return 0;
}

// 贪心算法求解豆子背包问题
double fractionalKnapsack(int W, Bean beans[], int n) {
    // 计算价值比率
    for(int i = 0; i < n; i++) {
        beans[i].ratio = (double)beans[i].value / beans[i].weight;
    }
    
    // 根据价值比率排序
    qsort(beans, n, sizeof(Bean), compare);
    
    int currentWeight = 0; // 当前重量
    double finalValue = 0.0; // 最终价值

    // 遍历豆子
    for(int i = 0; i < n; i++) {
        if(currentWeight + beans[i].weight <= W) {
            currentWeight += beans[i].weight;
            finalValue += beans[i].value;
        } else {
            int remain = W - currentWeight;
            finalValue += beans[i].ratio * remain; // 取一部分
            break;
        }
    }

    return finalValue;
}

int main() {
    Bean beans[] = {{60, 10}, {100, 20}, {120, 30}};
    int W = 50; // 背包容量
    int n = sizeof(beans)/sizeof(beans[0]);
    printf("Maximum value we can obtain = %lf", fractionalKnapsack(W, beans, n));
    return 0;
}