c语言贪心算法求解背包问题

背包问题是一个经典的组合优化问题，贪心算法是其中一种有效的解法。

假设有一个容量为 W 的背包和 n 个物品，每个物品有其重量 w[i] 和价值 v[i]，我们的目标是在不超过背包容量的情况下，选择哪些物品可以使得背包中的总价值最大。

贪心算法的基本思路是，每次选择当前剩余空间能够容纳的具有最大单位价值的物品放入背包中，直到背包装满或者所有物品都已经被选择。具体的实现步骤如下：

1. 计算每个物品的单位价值，即 v[i]/w[i]。
2. 将所有物品按照单位价值从大到小排序。
3. 依次选取排序后的物品放入背包中，直到背包装满或者所有物品都已经被选择。

以下是使用 C 语言实现的贪心算法代码：

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

// 物品结构体
typedef struct {
    int weight; // 重量
    int value;  // 价值
} Item;

// 比较函数，用于排序
int compare(const void *a, const void *b) {
    Item *item1 = (Item *)a;
    Item *item2 = (Item *)b;
    double ratio1 = (double)item1->value / item1->weight;
    double ratio2 = (double)item2->value / item2->weight;
    if (ratio1 < ratio2) {
        return 1;
    } else if (ratio1 > ratio2) {
        return -1;
    } else {
        return 0;
    }
}

// 贪心算法
int knapsack(Item items[], int n, int capacity) {
    // 按照单位价值从大到小排序
    qsort(items, n, sizeof(Item), compare);
    int total_value = 0;
    for (int i = 0; i < n; i++) {
        if (capacity < items[i].weight) {
            // 当前物品无法完全放入背包中
            total_value += (double)capacity / items[i].weight * items[i].value;
            break;
        } else {
            // 当前物品可以完全放入背包中
            capacity -= items[i].weight;
            total_value += items[i].value;
        }
    }
    return total_value;
}

int main() {
    Item items[] = {{2, 10}, {3, 5}, {5, 15}, {7, 7}, {1, 6}, {4, 18}, {1, 3}};
    int n = sizeof(items) / sizeof(Item);
    int capacity = 15;
    int total_value = knapsack(items, n, capacity);
    printf("Total value: %d\n", total_value);
    return 0;
}

在上面的例子中，我们使用了一个 items 数组来存储所有的物品，其中每个元素是一个 Item 结构体，包含了物品的重量和价值。我们通过调用 knapsack 函数来求解最大价值，其中 n 是物品的个数，capacity 是背包的容量。在函数内部，我们使用 qsort 函数将所有物品按照单位价值从大到小排序，然后依次将能够放入背包的物品放入背包中，直到背包装满或者所有物品都已经被选择。最后返回背包中物品的总价值。