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

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

#include <stdio.h>

#define N 5 // 物品数量
#define C 10 // 背包容量

typedef struct {
    int w; // 物品重量
    int v; // 物品价值
    float r; // 物品价值重量比
} Item;

int main() {
    Item items[N] = {
        {2, 6, 0},
        {2, 3, 0},
        {6, 5, 0},
        {5, 4, 0},
        {4, 6, 0}
    }; // 物品数组

    // 计算每个物品的价值重量比
    for (int i = 0; i < N; i++) {
        items[i].r = (float) items[i].v / items[i].w;
    }

    // 按照价值重量比从大到小排序
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (items[i].r < items[j].r) {
                Item temp = items[i];
                items[i] = items[j];
                items[j] = temp;
            }
        }
    }

    int used[N] = {0}; // 标记每个物品是否被使用
    int weight = 0; // 当前背包的重量
    int value = 0; // 当前背包的价值

    // 贪心选择物品
    for (int i = 0; i < N; i++) {
        if (weight + items[i].w <= C) {
            used[i] = 1;
            weight += items[i].w;
            value += items[i].v;
        }
    }

    // 输出结果
    printf("物品\t重量\t价值\n");
    for (int i = 0; i < N; i++) {
        if (used[i]) {
            printf("%d\t%d\t%d\n", i + 1, items[i].w, items[i].v);
        }
    }
    printf("总重量：%d\n", weight);
    printf("总价值：%d\n", value);

    return 0;
}

上述代码实现了按照物品价值重量比从大到小排序，然后依次选取物品放入背包中，直到背包不能再放入物品为止。