问题概述
我们的目标是设计一个函数，该函数接收一个整数 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
-
处理 2：
- n = 2 >= 2，result.add(2)，n = 2 - 2 = 0。result = [5, 5, 2]。
- n = 0
-
处理 1：
- n = 0
- 返回： 最终结果为 [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 change(int n) {
// 使用ArrayList来存储结果，因为它提供了动态大小的特性
List 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
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”的问题。这种方法直观易懂，且对于给定的面额组合能够保证找到最优解。理解其背后的逻辑和适用场景，对于解决类似的组合优化问题至关重要。
