c语言贪心算法背包问题

背包问题是一类经典的优化问题，贪心算法是其中的一种解法。

具体来说，假设有一个背包，它的总容量为W，现在有n个物品，每个物品有一个重量wi和一个价值vi。要求选出一些物品放入背包中，使得它们的总重量不超过W，且它们的总价值最大。

贪心算法的思路是，按照每个物品的单位价值（即vi/wi）从大到小排序，然后依次将单位价值高的物品放入背包中，直到背包无法再放下下一个物品为止。

下面是C语言实现：

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

typedef struct {
    int weight; // 物品重量
    int value;  // 物品价值
} Item;

int cmp(const void *a, const void *b) {
    Item *ia = (Item *)a;
    Item *ib = (Item *)b;
    return (ib->value / ib->weight) - (ia->value / ia->weight);
}

int knapsack(Item *items, int n, int W) {
    qsort(items, n, sizeof(Item), cmp); // 按单位价值排序
    int cur_weight = 0; // 当前背包重量
    int cur_value = 0;  // 当前背包价值
    for (int i = 0; i < n; i++) {
        if (cur_weight + items[i].weight <= W) { // 如果可以放下当前物品
            cur_weight += items[i].weight;
            cur_value += items[i].value;
        } else { // 否则只放入能容纳的部分
            int remain = W - cur_weight;
            cur_value += items[i].value * ((double)remain / items[i].weight);
            break;
        }
    }
    return cur_value;
}

int main() {
    Item items[] = {{2, 10}, {3, 15}, {5, 20}, {7, 25}, {9, 30}};
    int n = sizeof(items) / sizeof(Item);
    int W = 15;
    int max_value = knapsack(items, n, W);
    printf("Max value: %d\n", max_value); // 输出最大价值
    return 0;
}

以上代码中，我们定义了一个Item结构体，表示每个物品的重量和价值；cmp函数用来按单位价值排序；knapsack函数是核心函数，它依次考虑每个物品，如果能放下就全部放入，否则只放入能容纳的部分。最后返回背包内物品的总价值。

在主函数中，我们定义了一个包含5个物品的数组和背包容量W=15，然后调用knapsack函数求解最大价值。