背包问题贪心算法c语言

背包问题是一个经典的动态规划问题，而不是贪心问题。但是，可以使用贪心算法来求解它的近似解。下面是一个使用贪心算法解决背包问题的 C 语言代码：

#include <stdio.h>

#define MAX_N 1000

typedef struct {
    double value;
    double weight;
} Item;

int n;
double capacity;
Item items[MAX_N];

int cmp(Item a, Item b) {
    return a.value / a.weight > b.value / b.weight;
}

double knapsack() {
    double ans = 0.0;
    int i;
    for (i = 0; i < n; ++i) {
        if (capacity >= items[i].weight) {
            capacity -= items[i].weight;
            ans += items[i].value;
        } else {
            ans += items[i].value * (capacity / items[i].weight);
            break;
        }
    }
    return ans;
}

int main() {
    int i;
    scanf("%d %lf", &n, &capacity);
    for (i = 0; i < n; ++i) {
        scanf("%lf %lf", &items[i].value, &items[i].weight);
    }
    qsort(items, n, sizeof(Item), cmp);
    printf("%.2f\n", knapsack());
    return 0;
}

该算法的思路是：按照每个物品的单位价值（即价值/重量）从大到小排序，然后依次将单位价值最高的物品放入背包中。如果当前物品的重量已经大于背包的剩余容量，那么就将该物品的一部分放入背包中，以填满背包。