用贪心算法解决背包问题c语言

背包问题是一个经典的优化问题，其中有一个固定大小的背包，一些物品具有不同的价值和大小。目标是将尽可能多的价值放入背包中，同时保持背包的大小不超过其容量。贪心算法是一种简单且有效的方法来解决背包问题。

以下是一个使用贪心算法解决背包问题的C语言代码：

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

typedef struct {
    int value;
    int weight;
} Item;

int compare(const void *a, const void *b) {
    double ratioA = ((Item*)a)->value / (double)((Item*)a)->weight;
    double ratioB = ((Item*)b)->value / (double)((Item*)b)->weight;
    if (ratioA > ratioB) {
        return -1;
    } else if (ratioA < ratioB) {
        return 1;
    } else {
        return 0;
    }
}

double getMaxValue(Item items[], int n, int capacity) {
    qsort(items, n, sizeof(Item), compare);
    double maxValue = 0.0;
    for (int i = 0; i < n; i++) {
        if (items[i].weight <= capacity) {
            maxValue += items[i].value;
            capacity -= items[i].weight;
        } else {
            maxValue += items[i].value * ((double)capacity / items[i].weight);
            break;
        }
    }
    return maxValue;
}

int main() {
    Item items[] = {{60, 10}, {100, 20}, {120, 30}};
    int capacity = 50;
    int n = sizeof(items) / sizeof(Item);
    double maxValue = getMaxValue(items, n, capacity);
    printf("The maximum value that can be put in a knapsack of capacity %d is %0.2f", capacity, maxValue);
    return 0;
}

这个程序中，我们首先定义了一个Item结构体，其中包含物品的价值和重量。然后我们定义了一个比较函数，它将物品按价值重量比的降序排序。接下来，我们定义了一个函数getMaxValue，它接受物品数组，物品数量和背包容量作为参数，并返回能够放入背包的最大价值。

在getMaxValue函数中，我们首先使用qsort函数对物品进行排序。然后，我们遍历物品数组，如果当前物品的重量小于等于背包的容量，我们将其放入背包中，并将背包容量减去物品重量。否则，我们将部分物品放入背包中，并停止遍历。

最后，在main函数中，我们定义了一些物品和背包容量，并调用getMaxValue函数来计算能够放入背包的最大价值。