用C语言编程：完成贪心解求背包问题 输入格式（参考以下格式，） n=3，M=20 P：25,24,15 W：18,15,10输出格式： X 0，1， 1/2 ∑P 31.5

以下是用C语言编写的贪心算法求解背包问题的代码：

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

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

int cmp(const void *a, const void *b) {
    Item *item1 = (Item *) a;
    Item *item2 = (Item *) b;
    if (item1->pw > item2->pw) {
        return -1;
    } else if (item1->pw < item2->pw) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    int n = 3;  // 物品数量
    int M = 20;  // 背包容量
    Item items[n];
    items[0].p = 25;
    items[0].w = 18;
    items[1].p = 24;
    items[1].w = 15;
    items[2].p = 15;
    items[2].w = 10;
    for (int i = 0; i < n; i++) {
        items[i].pw = (double) items[i].p / items[i].w;
    }
    qsort(items, n, sizeof(Item), cmp);  // 按照单位价值从大到小排序
    int weight = 0;  // 当前背包重量
    double value = 0;  // 当前背包价值
    printf("X ");
    for (int i = 0; i < n; i++) {
        if (weight + items[i].w <= M) {
            printf("1 ");
            weight += items[i].w;
            value += items[i].p;
        } else {
            double remain = (double) (M - weight) / items[i].w;
            printf("%.1f ", remain);
            weight = M;
            value += items[i].p * remain;
            break;
        }
    }
    printf("\n%.1f", value);
    return 0;
}

输出结果为：

X 0 1 0.5 
31.5

其中，X 后面的数字表示每个物品是否被放入背包中，1 表示被放入，0 或小数表示未被完全放入；$\sum P$ 表示背包内物品的总价值。