01背包贪心算法c语言

01背包问题是经典的动态规划问题，它的主要思想是在有限的容量下，选择一些物品放入背包中，以使得背包中所放物品的总价值最大化。而贪心算法则是通过每次选择当前最优的解，来逐步逼近全局最优解的一种算法。

01背包问题的贪心算法可以采用按单位重量价值降序排序的贪心策略：每次选择单位重量价值最高的物品放入背包中，直到背包装满为止。这样可以保证每次选择的物品都是当前最优的，但是并不能保证一定能得到全局最优解。

下面是01背包问题的贪心算法的C语言实现代码：

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

#define MAX_N 1000
#define MAX_C 1000

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

int cmp(const void* a, const void* b) {
    Item* ia = (Item*) a;
    Item* ib = (Item*) b;
    if (ia->r > ib->r) {
        return -1;
    } else if (ia->r < ib->r) {
        return 1;
    } else {
        return 0;
    }
}

int knapsack(Item* items, int n, int c) {
    qsort(items, n, sizeof(Item), cmp);
    int i, j;
    int total_v = 0;
    for (i = 0; i < n; i++) {
        if (items[i].w <= c) {
            total_v += items[i].v;
            c -= items[i].w;
        } else {
            total_v += items[i].v * c / items[i].w;
            break;
        }
    }
    return total_v;
}

int main() {
    int n, c;
    scanf("%d%d", &n, &c);
    Item items[MAX_N];
    int i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &items[i].w, &items[i].v);
        items[i].r = (double) items[i].v / items[i].w;
    }
    printf("%d\n", knapsack(items, n, c));
    return 0;
}