实现最小整数组合求和的贪心算法

作者 2025年8月30日 9

本文将详细介绍如何使用贪心算法，从给定面额（5、2、1）中选出最少数量的整数，使其总和等于目标整数n。我们将通过逐步分析、代码示例和注意事项，帮助读者理解并实现这一经典的找零问题解决方案。

问题概述

我们的目标是设计一个函数，该函数接收一个整数 n 作为输入，并返回一个 Integer 类型的列表。这个列表中的元素只能是 5、2 或 1，并且它们的总和必须等于 n。最关键的要求是，所返回的列表应包含最少数量的整数。

例如：

当 n = 12 时，输出应为 [5, 5, 2] (5+5+2 = 12)。
当 n = 3 时，输出应为 [2, 1] (2+1 = 3)。

这是一个经典的找零问题（Coin Change Problem）的简化版本，其中我们只有特定面额的“硬币”（5、2、1）。

核心逻辑：贪心算法

对于给定的面额（5、2、1），我们可以采用贪心算法来找到最优解。贪心算法的核心思想是：在每一步都选择当前看来最优的选项，希望最终能够得到全局最优解。在这个问题中，“当前最优”意味着优先使用最大面额的整数，直到无法再使用为止，然后转向次大面额，依此类推。

为什么贪心算法在这里有效？

面额5优先： 5是最大的面额。如果我们可以使用5，那么使用它总是比使用多个2和1来凑出5更优（例如，一个5比两个2和一个1更少）。
面额2次之： 在5无法使用后，2是最大的面额。使用2总是比使用两个1更优。
面额1最后： 1是最小面额，它确保我们总能凑出任何剩余的金额（只要 n 是非负整数）。

因此，算法的步骤如下：

尽可能多地使用 5： 只要 n 大于或等于 5，就将 5 添加到结果列表中，并从 n 中减去 5。
尽可能多地使用 2： 在 5 无法再使用后，只要 n 大于或等于 2，就将 2 添加到结果列表中，并从 n 中减去 2。
尽可能多地使用 1： 在 2 无法再使用后，只要 n 大于或等于 1，就将 1 添加到结果列表中，并从 n 中减去 1。
当 n 最终变为 0 时，结果列表就是我们需要的答案。

示例演练

让我们以 n = 12 为例，逐步演示这个过程：

初始化： n = 12，结果列表 result = []。
处理 5：
- n = 12 >= 5，result.add(5)，n = 12 – 5 = 7。result = [5]。
- n = 7 >= 5，result.add(5)，n = 7 – 5 = 2。result = [5, 5]。
- n = 2 < 5，停止使用 5。
处理 2：
- n = 2 >= 2，result.add(2)，n = 2 – 2 = 0。result = [5, 5, 2]。
- n = 0 < 2，停止使用 2。
处理 1：
- n = 0 < 1，停止使用 1。
返回： 最终结果为 [5, 5, 2]。

代码实现

以下是使用 Java 语言实现上述逻辑的函数：

import java.util.ArrayList; import java.util.List;  public class CoinChanger {      /**      * 计算给定整数n所需的最小数量的5、2、1面额的组合。      *      * @param n 目标整数      * @return 包含组合整数的列表      */     public static List<Integer> change(int n) {         // 使用ArrayList来存储结果，因为它提供了动态大小的特性         List<Integer> result = new ArrayList<>();          // 优先使用面额为5的整数         while (n >= 5) {             result.add(5);             n -= 5;         }          // 其次使用面额为2的整数         while (n >= 2) {             result.add(2);             n -= 2;         }          // 最后使用面额为1的整数，确保能凑齐所有剩余金额         while (n >= 1) {             result.add(1);             n -= 1;         }          return result;     }      public static void main(String[] args) {         // 测试用例         System.out.println("n = 12, Output: " + change(12)); // 预期: [5, 5, 2]         System.out.println("n = 55, Output: " + change(55)); // 预期: [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] (11个5)         System.out.println("n = 3, Output: " + change(3));   // 预期: [2, 1]         System.out.println("n = 0, Output: " + change(0));   // 预期: []         System.out.println("n = 7, Output: " + change(7));   // 预期: [5, 2]         System.out.println("n = 1, Output: " + change(1));   // 预期: [1]     } }

注意事项

List 与 Array 的区别： 在 Java 中，List（例如 ArrayList）和数组（Array）是不同的数据结构。数组在创建时大小固定，而 ArrayList 是动态的，可以根据需要自动扩容。对于这种需要不断添加元素的场景，ArrayList 是更合适的选择。初始化 ArrayList 的正确方式是 List<Integer> list = new ArrayList<>();。
贪心算法的适用性： 虽然贪心算法在这个特定问题（面额为 5, 2, 1）中是有效的，但它并非适用于所有找零问题。例如，如果面额是 [1, 3, 4]，目标金额是 6：
- 贪心算法会选择 [4, 1, 1]（3个硬币）。
- 最优解是 [3, 3]（2个硬币）。这说明贪心算法的有效性取决于硬币面额的特性。对于标准货币系统或本例中的 [5, 2, 1] 组合，贪心算法是正确的。
输入校验： 教程中的代码假设 n 是一个非负整数。在实际应用中，可能需要添加输入校验来处理负数或其他无效输入。如果 n 为负数，当前的实现会返回一个空列表，这可能不是预期的行为。

总结

通过采用贪心算法，我们可以高效且准确地解决“用最少数量的 5、2、1 整数凑成目标金额 n”的问题。这种方法直观易懂，且对于给定的面额组合能够保证找到最优解。理解其背后的逻辑和适用场景，对于解决类似的组合优化问题至关重要。

Hello! 欢迎来到悠悠畅享网！