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

问题概述

我们的目标是设计一个函数，该函数接收一个整数 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 是非负整数）。

因此，算法的步骤如下：

腾讯智影-AI数字人

基于AI数字人能力，实现7*24小时AI数字人直播带货，低成本实现直播业务快速增增，全天智能在线直播

73

查看详情

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

示例演练

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

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

注意事项

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

总结

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

以上就是实现最小整数组合求和的贪心算法的详细内容，更多请关注php中文网其它相关文章！