贪心算法解决高精度正整数问题

"解决问题的贪婪策略-贪心算法c语言版" 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。在解决某些特定类型的问题时，贪心算法能够有效地找到近似最优解或最优解。它通过每一步的局部最优决策来逐步构造全局最优解。 在标题提到的例子中，贪心算法被用来解决找零问题。通常，当我们拥有不同面额的硬币时，贪心算法会选择面额最大的硬币优先，以此类推，直到凑够所需的总金额。然而，这个策略并不总是最优的，正如描述中指出的，如果硬币的面额是100, 70, 50, 20, 10, 7, 5, 2, 1，并且需要找140元，贪心算法会给出100元一张、20元两张的组合，总共三张，但实际上是不最优的，因为两张70元的组合更优。 贪心算法的核心在于其无后向性，即每个步骤的决策不会影响之前步骤的决策。然而，对于某些问题，如上述找零问题，贪心策略无法保证全局最优解，这时就需要使用其他算法，如动态规划，来找出真正的最优解。 在描述中提到的《第四章》内容，讨论了一个高精度正整数问题，需要在保留的数字中构造出最小的正整数。这个问题可以通过贪心策略解决，即从高位到低位，每次都选择尽可能小的数字。然而，需要注意的是，问题分析部分强调了在实施贪婪策略时，需要考虑各种情况，例如当相邻位的数字大小关系不能确定最优解时，可能需要向前回溯比较，或者在没有删除任何数字的情况下，考虑从后面开始删除。在设计算法时，需要通过枚举多种实例来确保算法的正确性。 总结起来，贪心算法在某些问题上能提供高效的解决方案，但并非适用于所有问题。在实际应用中，理解问题的特性，以及贪心策略是否能保证全局最优，是非常重要的。对于不能用贪心解决的问题，应当寻求其他算法，如动态规划等。在编程实现过程中，充分的实例分析和测试是保证算法正确性的关键。