贪心算法解决背包问题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 > 0 ? 1 : -1;
}

int main() {
    int n, m; // 物品数量和背包容量
    Item items[MAX_N];
    double ans = 0.0; // 最大价值

    // 读入数据
    scanf("%d%d", &n, &m);
    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);

    // 贪心选择物品
    for (int i = 0; i < n; i++) {
        if (m < items[i].w) { // 背包容量不足以装下当前物品
            ans += m * items[i].r; // 只能装下一部分物品
            break;
        } else { // 背包容量足够装下当前物品
            ans += items[i].v; // 直接装下该物品
            m -= items[i].w;
        }
    }

    // 输出结果
    printf("%.2lf\n", ans);

    return 0;
}

该代码使用结构体数组来存储物品的重量、价值和单位价值，然后按照单位价值从大到小排序，最后使用贪心算法选择物品，直到背包容量不足以装下下一个物品为止。