贪心法求解部分背包问题C语言

部分背包问题是指，有一个背包容量为C，有n个物品，每个物品有一个重量wi和一个价值vi，可以取走物品的一部分，求背包所能装下的最大价值。

贪心法求解部分背包问题的思路是，按照每个物品的单位重量价值从大到小排序，然后依次装入物品，直到背包装满为止。如果当前物品无法完全装入背包，则将其部分装入，直到背包装满。

以下是部分背包问题的C语言代码实现：

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

typedef struct {
    double weight; // 物品重量
    double value; // 物品价值
    double unit_value; // 物品单位重量价值
} Item;

// 按照物品单位重量价值从大到小排序
int cmp(const void *a, const void *b) {
    Item *item1 = (Item *)a;
    Item *item2 = (Item *)b;
    return (item2->unit_value - item1->unit_value) > 0 ? 1 : -1;
}

int main() {
    int n = 5; // 物品数量
    int C = 10; // 背包容量
    Item items[n];
    items[0] = (Item){2, 6, 0};
    items[1] = (Item){2, 3, 0};
    items[2] = (Item){6, 5, 0};
    items[3] = (Item){5, 4, 0};
    items[4] = (Item){4, 6, 0};

    // 计算每个物品的单位重量价值
    for (int i = 0; i < n; i++) {
        items[i].unit_value = items[i].value / items[i].weight;
    }

    // 按照物品单位重量价值从大到小排序
    qsort(items, n, sizeof(Item), cmp);

    double value = 0; // 背包所能装下的最大价值
    int i = 0; // 当前物品下标
    while (C > 0 && i < n) {
        if (C >= items[i].weight) {
            value += items[i].value;
            C -= items[i].weight;
        } else {
            value += C * items[i].unit_value;
            C = 0;
        }
        i++;
    }

    printf("背包所能装下的最大价值为%f\n", value);

    return 0;
}

在实现中，首先定义了一个Item结构体来存储物品的重量、价值和单位重量价值。然后计算每个物品的单位重量价值，并按照从大到小的顺序排序。最后依次取出每个物品，如果能够完全装入背包，则将其全部装入；否则，将其部分装入，直到背包装满为止。最终输出背包所能装下的最大价值。