编辑代码

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

// 定义豆子结构体，包括重量和价值
typedef struct {
    int weight;
    int value;
} Bean;

// 比较函数，用于按单位价值从大到小排序
int cmp(const void* a, const void* b) {
    Bean* beanA = (Bean*)a;
    Bean* beanB = (Bean*)b;
    double ratioA = (double)beanA->value / beanA->weight;
    double ratioB = (double)beanB->value / beanB->weight;
    if (ratioA < ratioB)
        return 1;
    else if (ratioA > ratioB)
        return -1;
    return 0;
}

// 贪心算法求解豆子背包问题的函数
double knapsack(int n, int capacity, Bean* beans) {
    // 按照单位价值从大到小排序
    qsort(beans, n, sizeof(Bean), cmp);
    
    double totalValue = 0.0; // 总价值
    int i;
    for (i = 0; i < n; i++) {
        if (beans[i].weight <= capacity) {
            // 当前豆子可以完整装入背包
            totalValue += beans[i].value;
            capacity -= beans[i].weight;
        } else {
            // 当前豆子只能部分装入背包
            totalValue += (double)beans[i].value * capacity / beans[i].weight;
            break;
        }
    }
    
    return totalValue;
}

// 主函数
int main() {
    int n; // 豆子数量
    int capacity; // 背包容量
    printf("请输入豆子数量和背包容量：");
    scanf("%d %d", &n, &capacity);
    
    Bean* beans = (Bean*)malloc(n * sizeof(Bean));
    printf("请分别输入每个豆子的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &beans[i].weight, &beans[i].value);
    }
    
    double totalValue = knapsack(n, capacity, beans);
    printf("背包所能装下的最大价值为：%lf\n", totalValue);
    
    free(beans);
    return 0;
}