编辑代码

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

typedef struct {
    double weight;  // 豆子的重量
    double value;   // 豆子的价值
} Bean;

// 比较函数：按照单位重量价值从高到低排序
int cmp(const void *a, const void *b) {
    Bean *bean1 = (Bean *) a;
    Bean *bean2 = (Bean *) b;
    double vpw1 = bean1->value / bean1->weight;
    double vpw2 = bean2->value / bean2->weight;
    if (vpw1 > vpw2) {
        return -1;
    } else if (vpw1 < vpw2) {
        return 1;
    } else {
        return 0;
    }
}

void knapsack_greedy(Bean *beans, int n, double capacity, double *total_value, Bean **selected_items) {
    if (n <= 0 || capacity <= 0) {
        *total_value = 0;
        *selected_items = NULL;
        return;
    }

    // 按照单位重量价值从高到低排序
    qsort(beans, n, sizeof(Bean), cmp);

    double curr_capacity = capacity;   // 当前背包剩余容量
    double curr_value = 0;             // 当前已选择豆子的总价值
    Bean *items = (Bean *) malloc(n * sizeof(Bean));  // 已选择的豆子列表
    int num_items = 0;

    // 根据贪心选择策略，依次将豆子放入背包中
    for (int i = 0; i < n && curr_capacity > 0; i++) {
        if (beans[i].weight <= curr_capacity) {  // 背包能够容纳当前豆子
            curr_capacity -= beans[i].weight;
            curr_value += beans[i].value;
            items[num_items++] = beans[i];
        }
    }

    *total_value = curr_value;
    *selected_items = items;
}

int main() {
    // 测试样例
    Bean beans[] = {{2, 3}, {3, 4}, {4, 5}, {5, 6}};
    int n = sizeof(beans) / sizeof(Bean);
    double capacity = 8;

    double total_value;
    Bean *selected_items;
    knapsack_greedy(beans, n, capacity, &total_value, &selected_items);

    printf("总的价值: %g\n", total_value);
    printf("Selected items:\n");
    for (int i = 0; i < n && selected_items != NULL; i++) {
        printf("重量: %g, 价值: %g\n", selected_items[i].weight, selected_items[i].value);
    }

    free(selected_items);
    return 0;
}