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

以下是基于贪心算法解决背包问题的 C 语言代码：

#include <stdio.h>

#define MAX_SIZE 100

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

// 贪心算法函数，返回背包能装下的最大价值
int greedy_knapsack(int W, struct Item items[], int n) {
    // 按照物品单位重量价值从大到小排序
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            double unit_value_i = (double) items[i].value / items[i].weight;
            double unit_value_j = (double) items[j].value / items[j].weight;
            if (unit_value_i < unit_value_j) {
                struct Item tmp = items[i];
                items[i] = items[j];
                items[j] = tmp;
            }
        }
    }

    int max_value = 0;
    int cur_weight = 0;
    // 依次将单位重量价值最大的物品放入背包，直到背包不能再装下为止
    for (int i = 0; i < n; i++) {
        if (cur_weight + items[i].weight <= W) {
            cur_weight += items[i].weight;
            max_value += items[i].value;
        } else {
            int remaining_weight = W - cur_weight;
            max_value += remaining_weight * ((double) items[i].value / items[i].weight);
            break;
        }
    }

    return max_value;
}

int main() {
    int W = 50; // 背包最大承重
    struct Item items[MAX_SIZE] = {
        {10, 60}, {20, 100}, {30, 120}
    };
    int n = 3; // 物品个数

    int max_value = greedy_knapsack(W, items, n);

    printf("背包能装下的最大价值为：%d\n", max_value);

    return 0;
}

注意，这里使用的是按照物品单位重量价值从大到小排序的贪心策略。具体实现中，可以使用冒泡排序或者快速排序等方法进行排序。