C语言通过贪心算法解决背包问题

背包问题是一个经典的组合优化问题，其目标是在限定的背包容量下，选择最有价值的物品装入背包中。贪心算法是一种常用的求解背包问题的方法，其基本思想是每次选择当前最优的物品装入背包中。

具体实现时，可以按照物品单位价值（即物品的价值除以重量）从大到小的顺序依次选择物品，直到背包容量被装满或所有物品都被选择完毕。如果当前物品不能完全装入背包，则可以选择部分装入。

下面是一个使用贪心算法解决背包问题的C语言实现示例：

#include <stdio.h>

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

// 背包容量和物品数量
#define MAX_WEIGHT 50
#define ITEM_NUM 5

// 物品列表
Item items[ITEM_NUM] = {
    {10, 60}, {20, 100}, {30, 120}, {40, 140}, {50, 160}
};

// 按照单位价值从大到小排序
void sortItems() {
    int i, j;
    Item temp;
    for (i = 0; i < ITEM_NUM - 1; i++) {
        for (j = i + 1; j < ITEM_NUM; j++) {
            if (items[i].value / items[i].weight < items[j].value / items[j].weight) {
                temp = items[i];
                items[i] = items[j];
                items[j] = temp;
            }
        }
    }
}

// 使用贪心算法求解背包问题
void knapsack() {
    int i, weight = 0, value = 0;
    sortItems();
    for (i = 0; i < ITEM_NUM; i++) {
        if (weight + items[i].weight <= MAX_WEIGHT) {
            weight += items[i].weight;
            value += items[i].value;
        } else {
            value += (MAX_WEIGHT - weight) * items[i].value / items[i].weight;
            break;
        }
    }
    printf("Total weight: %d, total value: %d\n", weight, value);
}

int main() {
    knapsack();
    return 0;
}

在上面的示例中，我们首先定义了一个物品结构体来表示每个物品的重量和价值。然后，我们定义了背包容量和物品数量，并初始化了物品列表。接下来，我们实现了一个按照单位价值从大到小排序的函数，并在主函数中调用该函数对物品列表进行排序。最后，我们使用贪心算法求解背包问题，并输出总重量和总价值。