贪心算法 C++

引言

贪心算法是一种简单而有效的算法设计方法，它通过局部最优解来构造全局最优解。在许多问题中，贪心算法能够提供快速的解决方案。然而，并不是所有问题都适合用贪心算法解决，了解何时使用它是至关重要的。本文将深入探讨贪心算法的概念、应用场景以及一些经典案例，最后给出相应的 C++ 实现。

贪心算法的基本概念

贪心算法的核心思想是每一步采取当前状态下的最优选择，而不考虑后续的影响。它的基本步骤包括：

选择性质：每个阶段的选择必须是局部最优的。
可行性：所做的选择必须满足问题的约束条件。
最优性：通过局部最优选择，最终得到全局最优解。

贪心算法的一般结构如下：

初始化
选择一个局部最优解
更新状态
重复步骤2和3，直到达到目标

贪心算法的应用场景

贪心算法广泛应用于各种优化问题，尤其是在以下几种场景中表现突出：

资源分配：如活动选择、任务调度等。
路径优化：如最短路径问题。
网络设计：如最小生成树。
货币找零：如硬币找零问题。

经典案例

活动选择问题

活动选择问题是经典的贪心算法问题。给定一组活动，每个活动都有开始和结束时间，目标是选择最多数量的互不重叠的活动。

示例

假设有以下活动：

活动1：开始时间0，结束时间6
活动2：开始时间1，结束时间4
活动3：开始时间3，结束时间5
活动4：开始时间5，结束时间7
活动5：开始时间8，结束时间9
活动6：开始时间5，结束时间9

选择的活动为活动2、活动4和活动5。

最小生成树（Prim算法）

在图论中，最小生成树是连接图中所有顶点的最小边权和的树。Prim算法是求解最小生成树的经典贪心算法。

示例

对于一个加权无向图，Prim算法从一个任意顶点开始，每次选择一条边，添加到生成树中，直到包含所有顶点。

Dijkstra算法

Dijkstra算法用于求解单源最短路径问题。给定一个图及其权重，该算法能够找到从起点到所有其他顶点的最短路径。

示例

在一个带权有向图中，Dijkstra算法通过更新每个节点的最短距离，最终得到从起点到其他节点的最短路径。

硬币找零问题

给定一定面值的硬币和一个总金额，目标是用最少数量的硬币找零。

示例

假设有硬币面值为1, 5, 10, 25的情况下，总金额为30，最佳组合可能是两枚10元和两枚5元。

C++实现示例

活动选择问题的实现

cppCopy Code
#include <iostream>
#include <vector>
#include <algorithm>

struct Activity {
    int start;
    int finish;
};

bool activityCompare(Activity s1, Activity s2) {
    return (s1.finish < s2.finish);
}

void activitySelection(Activity arr[], int n) {
    std::sort(arr, arr + n, activityCompare);
    std::cout << "Selected activities: " << std::endl;

    int i = 0;
    std::cout << "(" << arr[i].start << ", " << arr[i].finish << ") ";
    
    for (int j = 1; j < n; j++) {
        if (arr[j].start >= arr[i].finish) {
            std::cout << "(" << arr[j].start << ", " << arr[j].finish << ") ";
            i = j;
        }
    }
}

int main() {
    Activity arr[] = {{0, 6}, {1, 4}, {3, 5}, {5, 7}, {8, 9}, {5, 9}};
    int n = sizeof(arr) / sizeof(arr[0]);
    activitySelection(arr, n);
    return 0;
}

Prim算法的实现

cppCopy Code
#include <iostream>
#include <vector>
#include <climits>

#define V 5

int minKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (mstSet[v] == false && key[v] < min) {
            min = key[v];
            min_index = v;
        }
    }
    return min_index;
}

void primMST(int graph[V][V]) {
    int parent[V];
    int key[V];
    bool mstSet[V];

    for (int i = 0; i < V; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    std::cout << "Edge \tWeight\n";
    for (int i = 1; i < V; i++)
        std::cout << parent[i] << " - " << i << "\t" << graph[i][parent[i]] << " \n";
}

int main() {
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };
    primMST(graph);
    return 0;
}

Dijkstra算法的实现

cppCopy Code
#include <iostream>
#include <vector>
#include <climits>

#define V 9

int minDistance(int dist[], bool sptSet[]) {
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++) {
        if (sptSet[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool sptSet[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    std::cout << "Vertex \tDistance from Source\n";
    for (int i = 0; i < V; i++)
        std::cout << i << "\t\t" << dist[i] << "\n";
}

int main() {
    int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
                        { 4, 0, 8, 0, 0, 0, 0, 11, 0 },
                        { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
                        { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
                        { 0, 0, 0, 9, 0, 10, 0, 0, 0 },
                        { 0, 0, 4, 14, 10, 0, 2, 0, 0 },
                        { 0, 0, 0, 0, 0, 2, 0, 1, 6 },
                        { 8, 11, 0, 0, 0, 0, 1, 0, 7 },
                        { 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
    dijkstra(graph, 0);
    return 0;
}

硬币找零问题的实现

cppCopy Code
#include <iostream>
#include <vector>
#include <algorithm>

void coinChange(int coins[], int m, int V) {
    std::sort(coins, coins + m); // Sort coins in ascending order
    std::vector<int> result;

    for (int i = m - 1; i >= 0 && V > 0; i--) {
        while (V >= coins[i]) {
            V -= coins[i];
            result.push_back(coins[i]);
        }
    }

    std::cout << "Coins used: ";
    for (int coin : result) {
        std::cout << coin << " ";
    }
}

int main() {
    int coins[] = {1, 5, 10, 25};
    int m = sizeof(coins) / sizeof(coins[0]);
    int V = 30; // Total amount
    coinChange(coins, m, V);
    return 0;
}

贪心算法的优缺点

优点

简单易懂：贪心算法的逻辑清晰，易于实现。
效率高：在许多情况下，贪心算法能快速找到解，时间复杂度较低。

缺点

不总是有效：贪心算法并不适用于所有问题，某些问题需要其他算法（如动态规划）来寻找最优解。
局部最优：贪心算法只能保证找到局部最优解，没有全局最优解的保证。

总结

贪心算法是一种强大且高效的算法设计策略，适用于特定类型的问题。通过理解贪心算法的基本原理及其应用场景，我们可以有效地解决许多实际问题。尽管贪心算法有其局限性，但在合适的场景中，它能发挥出极大的优势。希望本文的实例及实现对大家学习贪心算法有所帮助。