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

背包问题是一个经典的动态规划问题，但是也可以使用贪心算法进行解决。贪心算法的思想是每次选择当前最优的解决方案，从而得到全局最优解。

以下是使用贪心算法解决背包问题的C语言代码：

#include<stdio.h>

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

// 比较函数，按照单位价值从大到小排序
int cmp(struct Item a, struct Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 < r2;
}

// 贪心算法解决背包问题
double knapsack(int W, struct Item arr[], int n)
{
    // 按照单位价值从大到小排序
    qsort(arr, n, sizeof(arr[0]), cmp);

    int cur_weight = 0; // 当前背包中物品总重量
    double cur_value = 0; // 当前背包中物品总价值

    for (int i = 0; i < n; i++)
    {
        // 如果加入当前物品不会超过背包容量，则加入
        if (cur_weight + arr[i].weight <= W)
        {
            cur_weight += arr[i].weight;
            cur_value += arr[i].value;
        }
        else
        {
            // 否则，加入部分当前物品
            int remain = W - cur_weight;
            cur_value += (double)arr[i].value * remain / arr[i].weight;
            break;
        }
    }

    return cur_value;
}

int main()
{
    int W = 50; // 背包容量
    struct Item arr[] = {{10, 60}, {20, 100}, {30, 120}}; // 物品数组
    int n = sizeof(arr) / sizeof(arr[0]); // 物品数量

    double max_value = knapsack(W, arr, n);
    printf("Maximum value we can obtain = %.2lf\n", max_value);

    return 0;
}

以上代码中，我们首先定义了一个物品结构体，包含物品的重量和价值。然后，我们定义了一个比较函数，按照单位价值从大到小排序。接着，我们使用qsort函数对物品数组进行排序。最后，我们使用贪心算法，依次将单位价值最大的物品加入背包中，直到背包容量达到上限或者所有物品都被加入背包中。最终，我们得到背包中物品的最大价值。