背包问题贪心算法c语言

背包问题是一个经典的问题，在贪心算法中也有应用。下面是一种基于贪心算法的解法。

给定一组物品，每个物品有一个重量和一个价值。现在有一个容量为W的背包，问你如何选择物品放入背包中，使得背包中物品的总价值最大。

算法思路：

1. 计算每个物品的单位价值（即价值除以重量）。

2. 按照单位价值从大到小排序。

3. 依次将物品放入背包中，直到背包容量达到上限或者物品全部放完。

代码实现：

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

#define N 100

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

// 比较函数，用于按照单位价值从大到小排序
int cmp(const void *a, const void *b) {
    const Item *pa = (const Item *)a;
    const Item *pb = (const Item *)b;
    if (pa->unit_value > pb->unit_value) {
        return -1;
    } else if (pa->unit_value < pb->unit_value) {
        return 1;
    } else {
        return 0;
    }
}

// 贪心算法解决背包问题
double knapsack(Item items[], int n, int W) {
    double max_value = 0.0; // 最大价值
    int i;
    for (i = 0; i < n; i++) {
        items[i].unit_value = (double)items[i].value / items[i].weight; // 计算单位价值
    }
    qsort(items, n, sizeof(Item), cmp); // 按照单位价值从大到小排序
    for (i = 0; i < n; i++) {
        if (W >= items[i].weight) { // 能放下当前物品
            max_value += items[i].value;
            W -= items[i].weight;
        } else { // 放不下当前物品
            max_value += (double)W / items[i].weight * items[i].value;
            break;
        }
    }
    return max_value;
}

int main() {
    int n, W;
    Item items[N];
    printf("请输入物品数量和背包容量：");
    scanf("%d%d", &n, &W);
    printf("请输入每个物品的重量和价值：\n");
    int i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &items[i].weight, &items[i].value);
    }
    double max_value = knapsack(items, n, W);
    printf("最大价值为：%.2lf\n", max_value);
    return 0;
}

以上代码中，我们先定义了一个Item结构体，表示每个物品的重量、价值和单位价值。在knapsack函数中，我们首先计算每个物品的单位价值，并且按照单位价值从大到小排序。然后我们依次将物品放入背包中，直到背包容量达到上限或者物品全部放完。最后返回背包中物品的总价值。

注意，以上代码中我们使用了库函数qsort来进行排序，需要包含头文件stdlib.h。