数据结构与算法 — 贪心算法

数据结构与算法

数据结构与算法是计算机科学中的两个核心概念，它们在软件开发和问题解决中起着至关重要的作用。

数据结构

数据结构是计算机中存储、组织和管理数据的方式，它能够帮助我们高效地访问和修改数据。不同的数据结构适用于不同类型的应用场景。

常见的数据结构包括：

• 数组：一种线性数据结构，用于存储具有相同类型的元素集合，每个元素在内存中占据连续的位置。
• 链表：由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。
• 栈：一种后进先出（LIFO）的数据结构，常用于管理函数调用、表达式求值等。
• 队列：一种先进先出（FIFO）的数据结构，适用于任务调度、缓冲处理等场景。
• 树：一种分层数据结构，由节点组成，每个节点可以有零个或多个子节点。
• 图：由顶点（节点）和边组成，可以表示多对多的关系，适用于网络分析、路径查找等。

算法

算法是解决特定问题的一系列步骤和规则。算法的性能通常通过时间复杂度和空间复杂度来衡量。算法的设计和选择对程序的效率有很大影响。

常见的算法类型包括：

• 排序算法：如快速排序、归并排序、堆排序等，用于将数据集合按特定顺序排列。
• 搜索算法：如二分搜索、深度优先搜索（DFS）、广度优先搜索（BFS）等，用于在数据结构中查找特定元素。
• 图算法：如Dijkstra算法、A*搜索算法、Prim算法和Kruskal算法等，用于解决图中的最短路径、最小生成树等问题。
• 动态规划：一种通过将问题分解为重叠的子问题来解决问题的方法，适用于具有最优子结构特性的问题。
• 分治算法：将问题分解为若干个规模较小的子问题，递归解决子问题后合并结果，适用于某些特定类型的优化问题。
• 贪心算法：基于贪心策略，这种策略在每一步选择中都采取当前状态下最优的局部解，希望通过一系列局部最优解最终构造出一个全局最优解。

贪心算法

贪心算法的原理是基于贪心策略，这种策略在每一步选择中都采取当前状态下最优的局部解，希望通过一系列局部最优解最终构造出一个全局最优解。贪心算法的核心思想可以概括为以下几点：

• 选择标准：根据问题定义一个选择标准，这个标准用于评价哪个选择是当前最优的。这个标准通常与问题的最终目标直接相关，例如最小化总成本或最大化总价值。

• 局部最优解：在每一步决策中，算法都会选择当前看起来最优的解决方案。这种选择是基于局部信息做出的，而不依赖于未来的信息。

• 无回溯：一旦做出了选择，贪心算法就不会撤销或回溯。这意味着算法的决策是一次性的，一旦确定，就会沿着这个方向继续前进。

• 迭代过程：贪心算法通常通过迭代过程逐步构建解决方案。在每一轮迭代中，算法都会根据选择标准选择最优的决策，直到达到问题的终止条件。

• 问题构造：贪心算法适用于某些特定类型的问题，这些问题可以通过贪心选择性质和最优子结构性质来解决。选择性质意味着局部最优选择可以确保全局最优解；子结构性质意味着问题的最优解包含其子问题的最优解。

贪心算法的适用性

贪心算法并不适用于所有问题。一个问题是否适合使用贪心算法，需要满足以下两个重要性质：

• 贪心选择性质：算法可以做出局部最优选择，并且这些局部最优选择能够导向全局最优解。这意味着选择过程中不需要考虑将来的后果，因为局部最优解总是能够导致全局最优解。

• 最优子结构性质：一个问题的最优解包含其子问题的最优解。这意味着问题可以通过解决其子问题并组合这些子问题的解来解决。

贪心算法应用场景

1. 最小生成树问题
   问题描述：给定一个带权的无向连通图，如何选择边构造一棵包含所有顶点且总权重最小的生成树。
   解决方案：
   1）Prim算法：从一个顶点开始，逐步增加新的边和顶点，每次都选择连接已选顶点和未选顶点之间权重最小的边。
   2）Kruskal算法：将所有边按权重从小到大排序，依次选择边，如果加入当前边不会形成环，则加入该边，直到所有顶点都被连接。

2. 背包问题
   问题描述：给定一组物品，每个物品有重量和价值，在限定的总重量内，选择一部分物品，使得总价值最大。
   解决方案：按照单位重量价值（价值/重量）从高到低排序，然后从最高单位重量价值的物品开始，尽可能选择物品，直到达到背包重量限制。

3. 活动选择问题
   问题描述：给定一系列活动，每个活动有开始时间和结束时间，选择最大的互不相交的活动集合。
   解决方案：将活动按结束时间从早到晚排序，然后选择第一个活动，之后每次都选择与已选活动不相交的最早结束的活动。

4. 哈夫曼编码（Huffman Coding）
   问题描述：如何为一组字符设计最优的二进制编码，使得编码的平均长度尽可能短。
   解决方案：
   1）统计每个字符出现的频率。
   2）将每个字符看作一个叶子节点，并根据频率创建一个优先队列（最小堆）。
   3）每次从优先队列中取出两个频率最小的节点，创建一个新的内部节点作为它们的父节点，其
   频率为两个子节点频率之和。
   4）将新创建的节点加入优先队列。
   5）重复步骤3和4，直到优先队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
   6）从根节点到每个叶子节点的路径就构成了字符的哈夫曼编码。

5. 找零问题
   问题描述：假设你是一名收银员，需要给顾客找零n元，你手头有各种面额的货币。如何用最少的硬币数找给顾客。
   解决方案：首先，确定货币的面额顺序，例如1元、5元、10元、20元、50元、100元。然后，从最大面额开始，尽可能多地使用该面额的硬币，直到剩余找零金额小于该面额，然后转向下一个较小的面额，重复此过程，直到找零完成。

6. 硬币问题（Coin Changing Problem）
   问题描述：给定不同面额的硬币和目标金额，如何用最少的硬币达到目标金额。
   解决方案：使用贪心算法的变种，每次选择当前可用的最大面额硬币，直到达到目标金额。注意，这种方法不总是能得到最优解，对于某些特定的硬币面额和目标金额，可能需要采用其他算法（如动态规划）来找到最优解。

找零问题 c++示例

假设我们有面额为 1, 5, 10, 20, 50, 100 的货币，现在需要给顾客找零 n 元。我们希望用最少的硬币数找给顾客。贪心算法的策略是每次都选择面值最大的货币，直到找零总额达到 n。

#include <iostream>
#include <vector>// 定义货币面额的数组
std::vector<int> denominations = {1, 5, 10, 20, 50, 100};// 贪心算法找零函数
int greedyChange(int amount, const std::vector<int>& denoms) {int count = 0; // 用于计数找零需要的硬币数量for (int i = denoms.size() - 1; i >= 0; --i) {// 尽可能多地使用当前最大面额的硬币int coins = amount / denoms[i];count += coins;amount -= coins * denoms[i];// 如果找零金额为0，则结束循环if (amount == 0) {break;}}return count;
}int main() {int amountToChange;std::cout << "Enter the amount to change: ";std::cin >> amountToChange;// 调用贪心算法函数，获取找零所需的硬币数量int coinCount = greedyChange(amountToChange, denominations);std::cout << "The minimum number of coins to change " << amountToChange<< " is: " << coinCount << std::endl;return 0;
}

在这个例子中，首先定义了一个货币面额的数组 denominations，然后实现了一个 greedyChange 函数，该函数接受需要找零的金额和货币面额数组作为参数。在函数中，从最大面额的货币开始，尽可能多地使用它，直到找零金额不足以再次使用当前面额的货币，然后转向下一个较小的面额。这个过程一直持续到找零金额为0。

在 main 函数中，我们获取用户输入的找零金额，然后调用 greedyChange 函数计算并输出所需的最小硬币数量。

这个代码示例展示了如何在C++中使用贪心算法来解决实际问题。需要注意的是，这个贪心算法只适用于找零问题中的特定情况，即货币面额的组合能够无限制地分割。对于不可分割的情况，如硬币问题，需要采用不同的贪心策略或者其他算法。