背包问题，贪心算法c语言

背包问题是一个经典的优化问题，它的目标是在限定的背包容量下，选择一些物品放入背包中，使得背包中物品的总价值最大。贪心算法是一种常用的解决背包问题的方法，它的思想是每次选择当前能够获得最大收益的物品放入背包中，直到背包无法再放入物品为止。以下是一个简单的背包问题的贪心算法的C语言实现：

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

#define MAX_N 1000

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

int cmp(const void *a, const void *b) {
    Item *ia = (Item *)a;
    Item *ib = (Item *)b;
    double va = (double)ia->value / ia->weight;
    double vb = (double)ib->value / ib->weight;
    return vb > va ? 1 : -1;
}

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

int main() {
    int n, capacity;
    Item items[MAX_N];
    scanf("%d%d", &n, &capacity);
    int i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &items[i].weight, &items[i].value);
    }
    printf("%d\n", knapsack(items, n, capacity));
    return 0;
}