算法--贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法在有最优子结构的问题中尤其有效，这意味着局部最优解能决定全局最优解。简单来说，贪心算法对每个子问题都做出选择，不能回退，这与动态规划不同，后者会保存以前的结果，并根据以前的结果对当前进行选择，有回退功能。

贪心算法的特点：

1. 局部最优选择：在每一步都做出在当前看来最优的选择，希望这些局部最优能导致全局最优解。
2. 无回退操作：一旦做出了选择，就不再回退，即不考虑以前的选择。

贪心算法适用的问题：
贪心算法适用于具有“贪心选择性质”的问题，即局部最优解能决定全局最优解。贪心算法不能保证求得的最后解是最佳的，也不能用来求最大或最小解的问题，只能求满足某些约束条件的可行解的范围。

贪心算法的应用实例包括：

• 找零问题：如何用最少的硬币找零。
• 最小生成树：如Kruskal算法和Prim算法。
• 单源最短路径：如Dijkstra算法。
• 任务调度问题：如何安排任务以减少等待时间或延迟。
• 压缩编码：如Huffman编码。

贪心算法的设计步骤：

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解。

虽然贪心算法相对简单易懂，但它并不总是能得到全局最优解，因此在使用时需要仔细分析问题是否适合采用贪心算法。

贪心算法可以用来解决背包问题的一种特殊形式——分数背包问题（Fractional Knapsack Problem），但对于经典的0-1背包问题，贪心算法通常无法保证找到最优解。

分数背包问题
在分数背包问题中，你可以将物品分割成任意大小，然后选择其中的一部分放入背包中，目标是最大化背包中物品的总价值，同时不超过背包的容量限制。对于这个问题，贪心算法是有效的，因为你可以按照物品的价值重量比（单位价值）来选择物品，优先选择单位价值最高的物品，直到背包装满为止。

0-1背包问题
对于0-1背包问题，每个物品只能整体选取或不选取，不能分割。这种情况下，贪心算法选择物品的策略可能无法得到最优解。例如，如果贪心算法只考虑物品的价值或重量，而不是价值重量比，那么它可能会错过更优的组合，因为一个轻而价值高的物品可能比几个重而价值低的物品更有价值。

对于0-1背包问题，最优解可能需要通过动态规划等方法来找到，因为贪心算法可能无法考虑到所有物品组合的总价值。
总结，贪心算法适用于分数背包问题，但对于0-1背包问题，它可能无法保证找到最优解。

以下是使用贪心算法解决分数背包问题的C语言实现。在这个实现中，我们首先根据物品的价值重量比（单位价值）对物品进行排序，然后按单位价值从高到低依次选择物品放入背包，直到背包容量达到限制。

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

// 定义物品结构体
typedef struct {
    float weight; // 物品重量
    float value;  // 物品价值
    float ratio;  // 价值重量比
} Item;

// 比较函数，用于排序
int compare(const void *s1, const void *s2) {
    Item *e1 = (Item *)s1;
    Item *e2 = (Item *)s2;
    return e2->ratio - e1->ratio > 0 ? 1 : -1; // 降序排序
}

// 贪心算法解决分数背包问题
float fractionalKnapsack(int W, Item arr[], int n) {
    // 按价值重量比排序
    qsort(arr, n, sizeof(arr[0]), compare);

    int curWeight = 0;  // 当前背包重量
    float finalvalue = 0.0; // 结果（总价值）

    // 遍历所有物品
    for (int i = 0; i < n; i++) {
        // 如果加入当前物品不超过最大重量，加入整个物品
        if (curWeight + arr[i].weight <= W) {
            curWeight += arr[i].weight;
            finalvalue += arr[i].value;
        } else {
            // 如果不能加入整个物品，加入背包能装下的部分
            int remain = W - curWeight;
            finalvalue += arr[i].value * ((float) remain / arr[i].weight);
            break; // 背包已满
        }
    }

    return finalvalue;
}

// 测试代码
int main() {
    int W = 50;  // 背包容量
    Item arr[] = {{10, 60}, {20, 100}, {30, 120}};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("最大价值为: %.2f", fractionalKnapsack(W, arr, n));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

这段代码首先定义了一个Item结构体来存储每个物品的重量、价值和价值重量比。compare函数用于根据价值重量比对物品进行降序排序。fractionalKnapsack函数实现了贪心算法，首先对物品按价值重量比进行排序，然后遍历排序后的物品数组，根据背包剩余容量决定是否将当前物品整个或部分加入背包。最后，函数返回背包中物品的最大总价值。