编辑代码

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

// 定义豆子的结构体
struct Bean {
    int weight;
    int value;
    float value_per_weight;
};

// 比较函数用于按照单位重量价值降序排序
int compare(const void *a, const void *b) {
    return ((struct Bean *)b)->value_per_weight - ((struct Bean *)a)->value_per_weight;
}

// 贪心算法解决豆子背包问题
void knapsack(struct Bean *beans, int num_beans, int capacity) {
    int i;
    
    // 计算单位重量价值
    for (i = 0; i < num_beans; i++) {
        beans[i].value_per_weight = (float)beans[i].value / beans[i].weight;
    }

    // 按照单位重量价值降序排序
    qsort(beans, num_beans, sizeof(struct Bean), compare);

    // 装入背包
    int current_capacity = capacity;
    for (i = 0; i < num_beans; i++) {
        if (current_capacity >= beans[i].weight) {
            printf("放入豆子：重量=%d, 价值=%d\n", beans[i].weight, beans[i].value);
            current_capacity -= beans[i].weight;
        }
    }
}

int main() {
    // 示例数据
    struct Bean beans[] = {
        {2, 10},
        {3, 5},
        {5, 15},
        {7, 7},
        {1, 6}
    };

    int num_beans = sizeof(beans) / sizeof(beans[0]);
    int capacity = 10;

    printf("背包问题解决方案：\n");
    knapsack(beans, num_beans, capacity);

    return 0;
}