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

背包问题是一个经典的优化问题，可以用贪心算法来解决。具体步骤如下：

1. 将物品按照单位重量的价值从大到小排序。
2. 选择单位重量价值最大的物品放入背包中，直到背包无法再放入物品为止。

以下是用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; 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;
            }
        }
    }
}

// 贪心算法解决背包问题
int knapsack(Item items[], int capacity) {
    int i;
    int total_value = 0;
    for (i = 0; i < N; i++) {
        if (capacity >= items[i].w) {
            total_value += items[i].v;
            capacity -= items[i].w;
        } else {
            total_value += capacity * items[i].r;
            break;
        }
    }
    return total_value;
}

int main() {
    Item items[N] = {{2, 10, 0}, {3, 5, 0}, {5, 15, 0}, {7, 7, 0}, {1, 6, 0}};
    int capacity = C;
    int total_value;
    int i;

    // 计算单位重量价值
    for (i = 0; i < N; i++) {
        items[i].r = (float) items[i].v / items[i].w;
    }

    // 排序
    sort(items);

    // 解决背包问题
    total_value = knapsack(items, capacity);

    printf("背包容量：%d，物品数量：%d\n", C, N);
    printf("物品列表：\n");
    for (i = 0; i < N; i++) {
        printf("物品%d：重量%d，价值%d，单位重量价值%.2f\n", i + 1, items[i].w, items[i].v, items[i].r);
    }
    printf("\n最大价值：%d\n", total_value);

    return 0;
}

运行结果：

背包容量：10，物品数量：5
物品列表：
物品1：重量2，价值10，单位重量价值5.00
物品2：重量3，价值5，单位重量价值1.67
物品3：重量5，价值15，单位重量价值3.00
物品4：重量7，价值7，单位重量价值1.00
物品5：重量1，价值6，单位重量价值6.00

最大价值：45