用C语言编写一个贪心法解背包问题的程序

在C语言中，我们可以使用贪心算法来解决一些优化问题，如背包问题。这里以0-1背包问题为例，假设我们有一个背包的最大容量`W`，以及一组物品，每个物品有自己的价值`values[i]`和重量`weights[i]`。贪心策略通常选择当前单位重量价值最高的物品放入背包，直到背包装满为止。以下是简单的C代码实现：

#include <stdio.h>
#define MAX_W 100 // 背包最大容量
#define MAX_N 50 // 物品最多数量

// 定义物品结构体
typedef struct {
    int weight;
    int value;
} Item;

void knapsack_greedy(int W, Item items[], int n) {
    int i, w;
    int total_value = 0;

    // 按照价值/重量比排序
    for (i = 0; i < n; i++) {
        for (w = i + 1; w < n; w++) {
            if ((items[w].value / items[w].weight) > (items[i].value / items[i].weight)) {
                Item temp = items[i];
                items[i] = items[w];
                items[w] = temp;
            }
        }
    }

    // 使用贪心策略填充背包
    for (i = 0, w = 0; w < W && i < n; i++) {
        if (items[i].weight <= W - w) { // 如果物品能完全放入背包
            total_value += items[i].value;
            w += items[i].weight;
        } else { // 否则取部分物品
            total_value += items[i].value * (W - w) / items[i].weight;
            break;
        }
    }

    printf("Total value with greedy approach: %d\n", total_value);
}

int main() {
    int W, N;
    Item items[MAX_N]; // 初始化物品数组

    // 输入背包容量和物品信息
    scanf("%d %d", &W, &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &items[i].weight, &items[i].value);
    }

    knapsack_greedy(W, items, N);
    return 0;
}