0/1 背包问题贪心算法求解及 C 语言实现

问题描述： 假设有 'N' 个物品，每个物品都有自己的重量 'w' 和价值 'v'。有一个容量为 'C' 的背包，需要选择一些物品放入背包中，使得背包中物品的总价值最大，且总重量不超过背包容量。

贪心算法思路：

排序： 将给定物品按单位重量价值从大到小排序，即 'v/w' 从大到小排序。
选取物品： 从排序后的物品列表中，依次选择单位重量价值最高的物品，直到背包容量被填满或所有物品都被选取。

代码实现：

#include <stdio.h>

#define N 4 // 物品个数
#define C 10 // 背包容量

// 物品结构体
ty typedef struct {
    int w; // 重量
    int v; // 价值
} Item;

// 按单位重量价值从大到小排序
void sort(Item *items, int n) {
    int i, j;
    Item tmp;
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if ((double)items[i].v / items[i].w < (double)items[j].v / items[j].w) {
                tmp = items[i];
                items[i] = items[j];
                items[j] = tmp;
            }
        }
    }
}

// 贪心算法求解
int knapsack(Item *items, int n, int c) {
    sort(items, n);
    int i, w = 0, v = 0;
    for (i = 0; i < n; i++) {
        if (w + items[i].w <= c) {
            w += items[i].w;
            v += items[i].v;
        } else {
            break;
        }
    }
    return v;
}

int main() {
    Item items[N] = {{4, 40}, {7, 42}, {5, 25}, {3, 12}};
    int v = knapsack(items, N, C);
    printf('贪心算法求解得到的近似解为：%d\n', v);
    return 0;
}

示例：

假设有 4 个物品，重量分别为 (4, 7, 5, 3)，价值分别为 (40, 42, 25, 12)，背包容量为 10。

按单位重量价值排序：
- (40/4) = 10
- (42/7) = 6
- (25/5) = 5
- (12/3) = 4
选取物品：
- 选择第一个物品，重量为 4，价值为 40，剩余容量为 6。
- 选择第二个物品，重量为 7，价值为 42，剩余容量为 -1（背包容量不足）。
- 选择第三个物品，重量为 5，价值为 25，剩余容量为 1（背包容量不足）。
贪心算法最终选择的物品为：第一个物品和第二个物品，总价值为 82。

注意：

贪心算法只能得到 0/1 背包问题的近似解，并不一定是最优解。对于某些情况，贪心算法得到的解可能与最优解相差较大。

总结：

贪心算法是一种简单高效的算法，可以用于求解 0/1 背包问题的近似解。尽管它不能保证得到最优解，但它能够快速得到一个较为合理的解。