背包问题贪心算法c语言代码

背包问题的贪心算法通常被称为“分数背包问题”，因为它允许我们将物品的一部分放入背包中。以下是使用贪心算法解决分数背包问题的C语言代码实现：

#include <stdio.h>

typedef struct {
    double value;
    double weight;
    double density; //物品的价值密度，即单位重量的价值
} Item;

void sortItems(Item items[], int n) {
    int i, j;
    Item temp;

    //根据物品的价值密度对物品进行排序
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (items[i].density < items[j].density) {
                temp = items[i];
                items[i] = items[j];
                items[j] = temp;
            }
        }
    }
}

double fractionalKnapsack(Item items[], int n, double capacity) {
    double totalValue = 0.0;
    int i;

    sortItems(items, n);

    for (i = 0; i < n; i++) {
        if (items[i].weight <= capacity) {
            totalValue += items[i].value;
            capacity -= items[i].weight;
        } else {
            totalValue += items[i].density * capacity;
            break;
        }
    }

    return totalValue;
}

int main() {
    Item items[] = {
        {60, 10, 6},
        {100, 20, 5},
        {120, 30, 4},
    };
    int n = sizeof(items) / sizeof(items[0]);
    double capacity = 50;

    double maxValue = fractionalKnapsack(items, n, capacity);

    printf("Maximum value: %.2f", maxValue);

    return 0;
}

在这个例子中，我们有三个物品，它们的价值、重量和价值密度分别为{60, 10, 6}，{100, 20, 5}和{120, 30, 4}。我们有一个容量为50的背包，我们需要找到可以放入背包的物品，使得总价值最高。我们使用fractionalKnapsack函数来计算最大价值。该函数首先使用sortItems函数根据物品的价值密度对物品进行排序。接下来，它遍历排序后的物品列表，并尝试将每个物品放入背包中。如果物品可以完全放入背包，则将其全部放入，并更新当前背包容量和总价值。如果物品无法完全放入背包，则只将部分物品放入，并更新总价值。最后，函数返回计算的总价值。