背包问题贪婪算法的C语言实现

以下是背包问题贪婪算法的C语言实现：

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

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

// 物品结构体
typedef struct {
    int w; // 物品重量
    int v; // 物品价值
    float r; // 物品单位价值
} Item;

// 按照物品单位价值从大到小排序
void sort(Item *items) {
    int i, j;
    Item temp;
    for (i = 0; i < N - 1; i++) {
        for (j = i + 1; j < N; j++) {
            if (items[i].r < items[j].r) {
                temp = items[i];
                items[i] = items[j];
                items[j] = temp;
            }
        }
    }
}

// 贪心算法求解背包问题
void knapsack(Item *items) {
    int i;
    int c = C; // 剩余背包容量
    float totalValue = 0; // 总价值
    for (i = 0; i < N; i++) {
        if (items[i].w <= c) { // 物品可以全部装入背包
            c -= items[i].w;
            totalValue += items[i].v;
        } else { // 物品只能部分装入背包
            totalValue += c * items[i].r;
            break;
        }
    }
    printf("背包问题贪婪算法的最大价值为：%.2f\n", totalValue);
}

int main() {
    Item items[N] = {{2, 12}, {1, 10}, {3, 20}, {2, 15}, {4, 25}}; // 物品重量和价值
    int i;
    for (i = 0; i < N; i++) {
        items[i].r = (float) items[i].v / items[i].w; // 计算物品单位价值
    }
    sort(items); // 按照物品单位价值从大到小排序
    knapsack(items); // 贪心算法求解背包问题
    return 0;
}