背包问题贪心算法c++

好的，背包问题的贪心算法主要有两种，一种是按照物品的价值密度来选择，即每个物品的单位重量价值尽可能大的先选；另一种是按照物品的重量来选择，即每次选择最轻的物品放入背包中。以下是第二种贪心算法的C语言实现代码：

#include <stdio.h>

#define N 100

struct Item {
    int weight;
    int value;
} items[N];

int cmp(const void* a, const void* b) {
    const struct Item* x = (const struct Item*)a;
    const struct Item* y = (const struct Item*)b;
    double r1 = (double)x->value / x->weight;
    double r2 = (double)y->value / y->weight;
    if (r1 < r2)
        return -1;
    else if (r1 > r2)
        return 1;
    else
        return 0;
}

double fractional_knapsack(int W, int n) {
    int i;
    double ans = 0.0;
    qsort(items, n, sizeof(struct Item), cmp);
    for (i = n - 1; i >= 0 && W > 0; --i) {
        if (items[i].weight <= W) {
            ans += items[i].value;
            W -= items[i].weight;
        } else {
            ans += (double)items[i].value * W / items[i].weight;
            W = 0;
        }
    }
    return ans;
}

int main() {
    int W = 50; // 背包总重量
    int n = 3; // 物品数量
    items[0].weight = 10;
    items[0].value = 60;
    items[1].weight = 20;
    items[1].value = 100;
    items[2].weight = 30;
    items[2].value = 120;
    double ans = fractional_knapsack(W, n);
    printf("最大价值为 %lf\n", ans);
    return 0;
}

这段代码实现了一个分数背包问题，即物品可以被分割成小块放入背包中。在代码中我们首先以物品的价值密度对物品进行排序，然后按照从大到小的顺序依次选择物品放入背包中，直到背包被放满或所有物品都被放完为止。