贪心算法圣诞老人的礼物c语言

贪心算法是一种求解最优解问题的算法，它在每一步选择中都采取在当前状态下最好或最优的选择，从而希望得到全局最优解。而贪心算法圣诞老人的礼物问题是这样一个问题：圣诞老人需要准备一些礼物，每个礼物都有重量和价值两个属性。他的袋子只能装载一定重量的礼物，如何选择礼物才能使得袋子里的礼物总价值最大呢？

一种贪心策略是按照每个礼物单位重量的价值排序，然后从单位价值高到低依次选择礼物放入袋子中，直到袋子装满为止。

以下是一个C语言实现的例子：

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

#define MAXN 1001

struct gift {
    int weight;
    int value;
    float unitValue;
} gifts[MAXN];

int cmp(const void *a, const void *b) {
    struct gift *pa = (struct gift*)a;
    struct gift *pb = (struct gift*)b;
    return (int)(pb->unitValue - pa->unitValue);
}

int main() {
    int n, w;
    scanf("%d %d", &n, &w);
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &gifts[i].weight, &gifts[i].value);
        gifts[i].unitValue = (float)gifts[i].value / gifts[i].weight;
    }
    qsort(gifts, n, sizeof(struct gift), cmp);
    int i = 0;
    float maxValue = 0.0;
    while (w > 0 && i < n) {
        if (gifts[i].weight <= w) {
            w -= gifts[i].weight;
            maxValue += gifts[i].value;
        } else {
            maxValue += gifts[i].unitValue * w;
            w = 0;
        }
        ++i;
    }
    printf("%.2f\n", maxValue);
    return 0;
}