c语言解决01背包贪心算法

在C语言中，解决01背包问题的贪心策略通常适用于物品价值和重量都是正整数的情况。经典的贪心法是“优先选择价值密度最大的物品”，即单位重量内的价值最高的物品放入背包。以下是简单的贪心算法步骤：

1. 定义两个数组，`values` 存储每个物品的价值，`weights` 存储每个物品的重量。
2. 对物品按照 `values[i] / weights[i]` 的值降序排序（可以先计算好这个比例再进行排序）。
3. 遍历排序后的物品列表，依次将每个物品添加到背包中，直到背包容量达到上限。

#include <stdio.h>
#define MAX_ITEMS 100
#define MAX_BAG_CAPACITY 50

// 比较函数，用于数组排序
int compare(const void *a, const void *b) {
    return ((Item *)a)->value / ((Item *)a)->weight - ((Item *)b)->value / ((Item *)b)->weight;
}

typedef struct Item {
    int value; // 物品价值
    int weight; // 物品重量
} Item;

void knapsack_greedy(int values[], int weights[], int n, int capacity) {
    Item items[MAX_ITEMS];
    for (int i = 0; i < n; ++i)
        items[i].value = values[i];
    for (int i = 0; i < n; ++i)
        items[i].weight = weights[i];

    qsort(items, n, sizeof(Item), compare);

    int total_weight = 0, total_value = 0;
    for (int i = 0; i < n && total_weight + items[i].weight <= capacity; ++i) {
        total_weight += items[i].weight;
        total_value += items[i].value;
    }

    printf("最大总价值: %d\n", total_value);
    printf("使用的物品和总重量:\n");
    for (int i = 0; i < n && total_weight > 0; ++i) {
        if (total_weight >= items[i].weight) {
            printf("%d: %d 克, %d 元\n", i+1, items[i].weight, items[i].value);
            total_weight -= items[i].weight;
        }
    }
}

int main() {
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};
    int n = sizeof(values) / sizeof(values[0]);
    int capacity = 50;
    knapsack_greedy(values, weights, n, capacity);
    return 0;
}

注意：上述算法并不是总是最优解，对于一些特殊问题它可能会得到次优结果。01背包问题的动态规划解决方案才是保证最优解的方法。