背包问题贪心算法C语言实现

背包问题是一个经典的组合优化问题，它可以用贪心算法来求解。下面是背包问题贪心算法的C语言实现：

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

#define MAX_N 1000

typedef struct {
    int w; // 物品重量
    int v; // 物品价值
    double r; // 物品单位价值
} Item;

int cmp(const void *a, const void *b) {
    Item *x = (Item *)a;
    Item *y = (Item *)b;
    return y->r > x->r ? 1 : -1;
}

int main() {
    int n, c; // n为物品数量，c为背包容量
    Item items[MAX_N];
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &items[i].w, &items[i].v);
        items[i].r = (double)items[i].v / items[i].w;
    }
    qsort(items, n, sizeof(Item), cmp); // 按照单位价值从大到小排序
    int ans = 0; // 最大价值
    for (int i = 0; i < n && c > 0; i++) {
        int amount = c / items[i].w; // 可以放入的数量
        ans += amount * items[i].v; // 加入背包的总价值
        c -= amount * items[i].w; // 更新背包容量
    }
    printf("%d\n", ans);
    return 0;
}