贪心算法背包问题c语言代码

下面是贪心算法解决背包问题的C语言代码：

#include <stdio.h>

#define MAX_N 1000

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

int n, W;  // 物品数量和背包容量
Item items[MAX_N];  // 物品数组

// 比较函数，按照单位重量价值从大到小排序
int cmp(const void* a, const void* b) {
    Item* pa = (Item*)a;
    Item* pb = (Item*)b;
    if (pa->d > pb->d) return -1;
    if (pa->d < pb->d) return 1;
    return 0;
}

// 贪心算法求解背包问题
double knapsack() {
    int i;
    double ans = 0.0;
    qsort(items, n, sizeof(Item), cmp);  // 按照单位重量价值排序
    for (i = 0; i < n; ++i) {
        if (W >= items[i].w) {  // 可以放入该物品
            W -= items[i].w;
            ans += items[i].v;
        } else {  // 只能放入部分该物品
            ans += W * items[i].d;
            break;
        }
    }
    return ans;
}

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

输入格式为：第一行是物品数量和背包容量，接下来每行是一个物品的重量和价值。输出格式为：背包能够装下的最大价值。