贪心算法简介

定义与基本概念

贪心算法是一种在每一步都做出局部最优选择的算法。它并不总能找到全局最优解，但针对特定问题，它能高效地提供接近最优或最优的解。贪心算法的吸引力在于其简单性和效率，特别适合解决优化问题。其核心思想是通过不断地做出当前看起来最好的选择，最终导向全局最优或接近最优的解。

贪心选择性质

贪心选择性质是贪心算法能够产生全局最优解的充分必要条件。简言之，如果一个问题中的最优解由一系列局部最优选择构成，那么贪心算法就能找到这个最优解。贪心选择性质需要满足两个条件：

1. 无后效性：每次选择只依赖当前状态，不考虑未来影响。
2. 局部最优到全局最优：若每次选择都是局部最优的，那么整个解过程最终导向全局最优解。

贪心算法基本步骤

识别问题特性

在应用贪心算法之前，首先确认问题是否具备贪心选择性质。这通常意味着分析问题的局部最优解是否能组合成全局最优解。

选择局部最优解

贪心算法的步骤基于每次选择局部最优解。确保每次选择不会破坏未来可能的选择。

证明全局最优解

确保算法的有效性，需要证明该算法能在解决问题时选择的局部最优解最终导向全局最优解。

贪心算法实例分析

最小生成树问题

Prim算法

假设有无向图，目标是找到最小生成树，即边的总权重最小，且连接所有顶点的无环子图。Prim算法是一种用于寻找最小生成树的贪心算法。

#include <vector>
#include <limits>
#include <iostream>
using namespace std;

const int INF = numeric_limits<int>::max();

void prim(vector<vector<pair<int, int>>> &graph, int start) {
    int n = graph.size();
    vector<int> key(n, INF);
    vector<bool> mstSet(n, false);
    vector<int> parent(n, -1);

    key[start] = 0;
    for (int count = 0; count < n - 1; count++) {
        int u = -1;
        for (int v = 0; v < n; v++) {
            if (!mstSet[v] && (u == -1 || key[v] < key[u])) {
                u = v;
            }
        }
        mstSet[u] = true;
        for (auto &edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (!mstSet[v] && weight < key[v]) {
                parent[v] = u;
                key[v] = weight;
            }
        }
    }

    cout << "Minimum spanning tree:" << endl;
    for (int v = 1; v < n; v++) {
        cout << parent[v] << " -> " << v << " weight: " << key[v] << endl;
    }
}

Kruskal算法

另一种寻找最小生成树的方法是Kruskal算法，它通过排序边的权重并依次加入最小权重的边，直到形成MST。

void kruskal(vector<vector<pair<int, int>>> &edges, int n) {
    sort(edges.begin(), edges.end()); // 排序边的权重

    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    int mstWeight = 0;
    int edgesCount = 0;
    int mstEdges = 0;

    for (auto &edge : edges) {
        int u = edge.first.second;
        int v = edge.first.first;
        int weight = edge.second;
        u = find(parent, u);
        v = find(parent, v);

        if (u != v) {
            parent[u] = v;
            mstWeight += weight;
            mstEdges++;
            if (mstEdges == n - 1) break;
        }
    }

    cout << "Minimum spanning tree weight: " << mstWeight << endl;
}

int find(vector<int> &parent, int i) {
    if (parent[i] != i) {
        parent[i] = find(parent, parent[i]);
    }
    return parent[i];
}

零钱兑换问题

零钱兑换问题是典型的贪心算法应用。目标是在给定一组硬币面额，找到支付特定金额所需的最少硬币数量。

int coinChange(vector<int> coins, int amount) {
    sort(coins.begin(), coins.end()); // 硬币面额从小到大排序
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0; // base case

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i - coin >= 0 && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

背包问题

背包问题是一个经典组合优化问题，针对不同的背包问题类型（完全背包、0/1背包、多重背包等），贪心算法可能或可能不适用。例如，在0/1背包问题中，贪心算法通常不能得到最优解。

贪心算法的局限性

并非所有问题都能用贪心算法找到最优解。贪心算法的局限性主要表现在：

• 选择局部最优解可能导致全局非最优解。
• 不能解决涉及多个决策层或需要未来信息来做出当前最优决策的问题。

解决问题的步骤指南

如何识别贪心策略适用性

• 分析问题是否有明显的局部最优性质。
• 检查问题是否符合贪心选择性质的条件。

设计贪心算法的流程

1. 定义状态：确定算法需要跟踪的信息。
2. 选择操作：确定每次选择的局部最优解。
3. 迭代更新：不断选择并更新状态，直到达到终止条件。
4. 验证算法：证明算法能收敛到全局最优解。

验证贪心算法的正确性

• 数学证明：通过数学归纳法或推导证明算法的正确性。
• 实例分析：展示算法如何工作及最终结果。
• 复杂性分析：分析算法的时间和空间复杂度。

实战练习与案例分享

实例问题与解题思路

问题：编写一个程序，对给定一系列分数，找出可以组成给定目标分数的最少数量的分数。

代码实现与解析

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
using namespace std;

pair<int, int> findGreatestCommonDivisor(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return {a, 1};
}

int main() {
    vector<pair<int, int>> fractions = {{1, 2}, {1, 3}, {1, 6}};
    int target = 2; // 目标分数

    int gcd = fractions[0].first * fractions[0].second;
    for (int i = 1; i < fractions.size(); i++) {
        int numerator = fractions[i].first;
        int denominator = fractions[i].second;
        int newGcd = gcd;
        while (gcd != 1) {
            numerator -= gcd * (numerator / gcd);
            if (numerator == 0) break;
            gcd = findGreatestCommonDivisor(gcd, numerator);
        }

        if (numerator != 0) {
            cout << "无法用给定分数组成目标分数" << endl;
            return 0;
        }

        if (gcd != 1 || denominator != 1) {
            gcd = lcm(gcd, denominator);
        }
        if (gcd < target) {
            gcd = lcm(gcd, fractions[i].second);
        }
        gcd = lcm(gcd, fractions[i].second);
        fractions[i] = {gcd, fractions[i].second};
        gcd = gcd;
    }

    gcd = 1;
    for (const auto &pair : fractions) {
        gcd = lcm(gcd, pair.second);
    }
    if (gcd < target) {
        cout << "无法用给定分数组成目标分数" << endl;
        return 0;
    }

    int count = 0;
    for (const auto &pair : fractions) {
        if (gcd % pair.first == 0) {
            count++;
        }
    }
    cout << "最少需要使用 " << count << " 个分数来组成目标分数" << endl;

    return 0;
}

// 求两个数的最小公倍数
int lcm(int a, int b) {
    return (a / findGreatestCommonDivisor(a, b).first) * b;
}

错误分析与优化建议

在上述代码中，我们首先计算出所有分数的最大公约数（GCD），然后尝试使用这些分数去组成目标分数。如果在任何步骤中无法用给定分数组合成目标分数，则输出不能完成。通过对分数的GCD进行计算，我们可以有效地减少计算量，优化算法效率。

总结

贪心算法是一种在优化问题中常用且高效的策略。通过理解和应用贪心选择性质，可以设计出高效且易于实现的算法。然而，识别问题是否符合贪心算法的适用条件至关重要，并且要认识到贪心算法的局限性。通过实践和分析，可以更好地掌握贪心算法的精髓，并在各种编程挑战中灵活运用。