贪心法解背包问题c语言

以下是使用贪心法解决背包问题的C语言代码：

#include <stdio.h>

#define MAX_N 1000

typedef struct {
    double w; // 物品重量
    double v; // 物品价值
    double ratio; // 价值重量比
} Item;

int n; // 物品数量
double m; // 背包容量
Item items[MAX_N]; // 物品数组

// 比较函数：按照价值重量比从大到小排序
int cmp(const void *a, const void *b) {
    Item *ia = (Item *) a;
    Item *ib = (Item *) b;
    return ib->ratio > ia->ratio ? 1 : -1;
}

// 贪心算法：返回能够放进背包的最大价值
double greedy() {
    double ans = 0; // 最大价值
    double weight = 0; // 当前背包重量
    for (int i = 0; i < n; i++) {
        if (weight + items[i].w <= m) { // 如果能够放进背包
            ans += items[i].v;
            weight += items[i].w;
        } else { // 否则只能放部分物品
            ans += (m - weight) * items[i].ratio;
            break;
        }
    }
    return ans;
}

int main() {
    scanf("%d %lf", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &items[i].w, &items[i].v);
        items[i].ratio = items[i].v / items[i].w;
    }
    qsort(items, n, sizeof(Item), cmp); // 按照价值重量比排序
    printf("%.2lf\n", greedy()); // 输出最大价值
    return 0;
}

该代码首先读入物品数量和背包容量，然后依次读入每个物品的重量和价值，并计算出价值重量比。接着按照价值重量比从大到小排序，然后使用贪心算法从大到小依次选取物品，直到背包装满或者所有物品都被选完。如果能够放进背包，则全部放入；否则只能放部分物品，使得背包恰好被装满。最后输出能够放进背包的最大价值。