贪心算法背包问题c

背包问题是一个经典的动态规划问题，但是也可以使用贪心算法来解决。贪心算法的思想是每次选取当前最优的解决方案，直到得到最终的解决方案。

在背包问题中，如果我们按照物品单位重量的价值进行排序，每次选择单位重量价值最高的物品放入背包中，直到背包无法再放入物品为止，那么得到的解就是最优解。

具体实现步骤如下：

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

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

3.依次将单位重量价值最高的物品放入背包中，直到背包无法再放入物品为止。

代码实现如下：

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

#define MAX_N 1000

struct item {
    int weight; // 物品重量
    int value; // 物品价值
    double vpw; // 物品单位重量价值
};

int cmp(const void *a, const void *b) {
    struct item *p1 = (struct item *)a;
    struct item *p2 = (struct item *)b;
    if (p1->vpw < p2->vpw)
        return 1;
    else if (p1->vpw > p2->vpw)
        return -1;
    else
        return 0;
}

int main() {
    int n, w; // n为物品数量，w为背包容量
    struct item items[MAX_N];
    scanf("%d %d", &n, &w);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &items[i].weight, &items[i].value);
        items[i].vpw = (double)items[i].value / items[i].weight;
    }
    qsort(items, n, sizeof(struct item), cmp);
    int ans = 0; // 背包能够装下的最大价值
    for (int i = 0; i < n && w > 0; i++) {
        if (w >= items[i].weight) {
            ans += items[i].value;
            w -= items[i].weight;
        } else {
            ans += (int)(w * items[i].vpw);
            w = 0;
        }
    }
    printf("%d\n", ans);
    return 0;
}

该算法的时间复杂度为 $O(n\log n)$，其中 n 为物品数量。