背包问题贪心算法c语言

背包问题是一个经典的动态规划问题，贪心算法并不一定能得到最优解。但是，如果背包问题的物品的体积和价值比比较固定，可以使用贪心算法求解。以下是使用贪心算法解决背包问题的C语言代码：

#include <stdio.h>

// 物品结构体
struct item {
    int value; // 价值
    int weight; // 重量
};

// 比较函数，按单位价值从大到小排序
int cmp(const void *a, const void *b) {
    struct item *ia = (struct item *)a;
    struct item *ib = (struct item *)b;
    double va = (double)ia->value / ia->weight;
    double vb = (double)ib->value / ib->weight;
    return (vb > va) - (vb < va);
}

// 贪心算法求解背包问题
double knapsack(int W, struct item items[], int n) {
    double total_value = 0.0;
    qsort(items, n, sizeof(struct item), cmp); // 按单位价值排序
    for (int i = 0; i < n; i++) {
        if (W >= items[i].weight) { // 可以放入整个物品
            total_value += items[i].value;
            W -= items[i].weight;
        } else { // 只能放入部分物品
            total_value += (double)W / items[i].weight * items[i].value;
            break;
        }
    }
    return total_value;
}

int main() {
    int W = 50; // 背包容量
    struct item items[] = {
        {60, 10},
        {100, 20},
        {120, 30},
    };
    int n = sizeof(items) / sizeof(items[0]); // 物品个数
    double total_value = knapsack(W, items, n);
    printf("Total value: %.2f\n", total_value);
    return 0;
}

上述代码中，`cmp`函数用于按单位价值从大到小排序，`knapsack`函数用于实现贪心算法，`main`函数中的`items`数组表示物品的价值和重量，`n`表示物品的个数，`W`表示背包的容量。运行结果为：

Total value: 240.00