三个例子让你彻底明白贪心算法【详细易懂】

贪心算法基础

基本思想

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。贪心算法在有最优子结构的问题中效果最好，也就是说局部最优解能决定全局最优解。

贪心算法的基本步骤如下：

1. 建模：将问题模型化，定义好问题的优化目标和约束条件。

2. 分解：将问题分解为一系列子问题。

3. 贪心策略：为每个子问题定义贪心策略，即如何在这一步做出最好的选择。

4. 解决：按照贪心策略解决每个子问题，并汇总为最终问题的解。

5. 分析验证：分析算法的正确性，验证算法的有效性。

经典贪心问题

问题一：活动选择问题

问题描述

给定一个活动时间集合，每个活动都有一个开始时间和一个结束时间。选择最大的活动子集合，使得所选活动间互不重叠。

解题思路

按照活动的结束时间对所有活动进行排序，然后依次选择每一个活动，在选择时，如果一个活动的开始时间大于或等于当前选择的活动的结束时间，则选择这个活动。

C++代码示例

#include <iostream>
#include <vector>
#include <algorithm>

// 定义一种活动结构体存储开始和结束时间
struct Activity {
    int start;
    int finish;
};

// 活动比较函数，用于排序
bool activityCompare(Activity s1, Activity s2) {
    return (s1.finish < s2.finish);
}

// 贪心选择在一系列活动中选取最大兼容子集
void selectMaxActivities(std::vector<Activity> &activities) {
    // 首先按结束时间对活动进行排序
    std::sort(activities.begin(), activities.end(), activityCompare);

    int n = activities.size();
    int i = 0; // 从第一个活动开始选择
    std::cout << "(" << activities[i].start << ", " << activities[i].finish << "), ";

    // 从第二个活动开始
    for (int j = 1; j < n; j++) {
        // 如果这个活动的开始时间大于或等于上个活动的结束时间，则选择该活动
        if (activities[j].start >= activities[i].finish) {
            std::cout << "(" << activities[j].start << ", " << activities[j].finish << "), ";
            i = j;
        }
    }
}

int main() {
    std::vector<Activity> activities = {{5, 9}, {1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};

    selectMaxActivities(activities);

    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

问题二：装载问题

问题描述

有一艘载重量为W的船和n个物品，每个物品有各自的重量，如何选择物品装上船从而让船的载重量最充分利用。

解题思路

按照物品的重量对所有物品进行排序，然后依次选择每一个物品，如果选择了这个物品船没有超载，则装载这个物品。

C++代码示例

#include <iostream>
#include <vector>
#include <algorithm>

// 比较函数用于物品的重量排序
bool compare(int a, int b) {
    return a < b; // 升序排序
}

// 贪心算法解决装载问题
void loadMaxWeight(std::vector<int> weights, int W) {
    // 按照重量对物品进行排序
    std::sort(weights.begin(), weights.end(), compare);

    int currentLoad = 0; // 当前载重量
    for (int i = 0; i < weights.size() && currentLoad < W; i++) {
        if (currentLoad + weights[i] <= W) {
            currentLoad += weights[i];
            std::cout << weights[i] << " ";
        }
    }
    std::cout << "\nTotal loaded weight: " << currentLoad << std::endl;
}

int main() {
    std::vector<int> weights = {10, 40, 20, 30};
    int W = 100;

    loadMaxWeight(weights, W);

    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

问题三：找零问题

问题描述

假设有面额为C = {c1, c2, ..., cm}的无限硬币，对于任意金额N，如何用最少的硬币数量构成N。

解题思路

先将硬币按面额从大到小排序，然后从面额最大的开始，尽可能多地选择每种硬币，直到无法再选择该种硬币或者已构成金额N。

C++代码示例

#include <iostream>
#include <vector>
#include <algorithm>

// 解决找零问题的贪心算法
void minCoins(std::vector<int> &coins, int N) {
    std::sort(coins.begin(), coins.end(), std::greater<int>()); // 从大到小排序
    std::vector<int> result; // 存储结果的向量

    for (int i = 0; i < coins.size(); i++) {
        while (N >= coins[i]) {
            N -= coins[i];
            result.push_back(coins[i]);
        }
    }

    for (int i = 0; i < result.size(); i++) {
        std::cout << result[i] << " ";
    }
}

int main() {
    std::vector<int> coins = {25, 10, 5, 1};
    int N = 63; // 想要找的总金额

    minCoins(coins, 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

以上代码分别展示了三个贪心算法的经典问题，每个问题都基于其特定的贪心策略来解决。贪心算法的关键是正确定义贪心策略并证明该策略可以得到全局最优解。在某些问题中，比如装载问题和找零问题，贪心算法是非常有效的。但在另一些问题，如0-1背包问题中，贪心策略可能就不能保证得到全局最优解。因此，设计贪心算法之前，验证它是否适用于特定问题是非常重要的。

如果你想更深入地了解人工智能的其他方面，比如机器学习、深度学习、自然语言处理等等，也可以点击这个链接，我按照如下图所示的学习路线为大家整理了100多G的学习资源，基本涵盖了人工智能学习的所有内容，包括了目前人工智能领域最新顶会论文合集和丰富详细的项目实战资料，可以帮助你入门和进阶。

链接： 人工智能交流群（大量资料）