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

背包问题是一个经典的动态规划问题，但也可以使用贪心算法来解决。在贪心算法中，我们尽可能选择单位重量价值最高的物品放入背包中，直到背包无法再容纳为止。

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

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

#define MAX_WEIGHT 100 // 背包的最大容量

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

// 比较函数，用于给物品按照单位重量价值排序
int cmp(const void* a, const void* b) {
    Item* itemA = (Item*)a;
    Item* itemB = (Item*)b;
    return (int)(itemB->ratio - itemA->ratio);
}

// 贪心算法解决背包问题
float knapsack(Item items[], int n, int maxWeight) {
    float totalValue = 0.0; // 背包中物品总价值

    // 按照单位重量价值从高到低排序
    qsort(items, n, sizeof(Item), cmp);

    // 依次将单位重量价值最高的物品放入背包中
    for (int i = 0; i < n && maxWeight > 0; i++) {
        if (items[i].weight > maxWeight) { // 物品无法全部放入背包中
            totalValue += items[i].value * (float)maxWeight / items[i].weight; // 加入部分物品的价值
            break;
        }
        else { // 物品可以全部放入背包中
            totalValue += items[i].value; // 加入全部物品的价值
            maxWeight -= items[i].weight; // 减少背包的剩余容量
        }
    }

    return totalValue; // 返回背包中物品的总价值
}

int main() {
    Item items[] = {{10, 60}, {20, 100}, {30, 120}}; // 物品数组
    int n = sizeof(items) / sizeof(items[0]); // 物品数量
    int maxWeight = MAX_WEIGHT; // 背包的最大容量

    float totalValue = knapsack(items, n, maxWeight); // 使用贪心算法求解背包问题

    printf("Total value in the knapsack is: %.2f\n", totalValue); // 输出背包中物品的总价值

    return 0;
}

以上代码使用了 qsort 函数来对物品按照单位重量价值从高到低排序。然后我们依次将单位重量价值最高的物品放入背包中，直到背包无法再容纳为止。如果某个物品无法全部放入背包中，则只加入部分物品的价值即可。最终输出背包中物品的总价值即可。