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

背包问题是一种经典的优化问题，在计算机科学领域中被广泛应用。其中有一种常见的背包问题是 0-1 背包问题，即给定一组物品，每种物品都有一个重量和一个价值，在限定的总重量内，选择若干件物品装入背包，使得装入背包中的物品总价值最大。

贪心算法求解 0-1 背包问题的基本思路是：对于每件物品，计算其单位重量的价值，然后按照单位重量价值从大到小进行排序，依次将单位重量价值较大的物品装入背包中，直到背包装满为止。

下面是 C 语言实现贪心算法解 0-1 背包问题的示例代码：

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

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

// 比较函数，按照单位重量价值从大到小进行排序
int cmp(const void *a, const void *b) {
    Item *p1 = (Item *)a;
    Item *p2 = (Item *)b;
    double r1 = (double)p1->value / p1->weight;
    double r2 = (double)p2->value / p2->weight;
    if (r1 < r2)
        return 1;
    else if (r1 > r2)
        return -1;
    else
        return 0;
}

// 贪心算法求解背包问题
int knapsack(Item items[], int n, int capacity) {
    // 按照单位重量价值从大到小进行排序
    qsort(items, n, sizeof(Item), cmp);

    int i, j, max_value = 0;
    for (i = 0; i < n && capacity > 0; i++) {
        // 如果当前物品可以放入背包中，则放入背包中
        if (items[i].weight <= capacity) {
            max_value += items[i].value;
            capacity -= items[i].weight;
        }
        // 否则，将当前物品按照比例分成两部分放入背包中
        else {
            max_value += (double)capacity / items[i].weight * items[i].value;
            break;
        }
    }
    return max_value;
}

int main() {
    Item items[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(items) / sizeof(Item);
    int capacity = 50;
    int max_value = knapsack(items, n, capacity);
    printf("背包最大价值为：%d\n", max_value);
    return 0;
}

在上述代码中，我们定义了一个 Item 结构体来表示每件物品的重量和价值。在 cmp 函数中，我们按照单位重量价值从大到小进行排序。在 knapsack 函数中，我们依次将单位重量价值较大的物品放入背包中，直到背包装满为止。如果当前物品不能完全放入背包中，则将其按照比例分成两部分放入背包中。

最后，我们在 main 函数中定义了 3 件物品和一个容量为 50 的背包，然后调用 knapsack 函数求解背包问题，并输出结果。

希望这个示例代码可以帮助你理解贪心算法求解背包问题的基本思路。