Java 贪心算法实现及找零钱示例

贪心算法是一种简单而有效的算法，它通过每次选择当前最优解来逐步构建最终解。在 Java 中实现贪心算法需要按照以下步骤进行：

确定问题的贪心策略，即每次选择当前最优解的规则。
通过编写一个函数来实现贪心策略，该函数应该能够根据当前状态选择最优的解决方案。
在主函数中使用循环来执行贪心策略，直到得到最终的解决方案。
对于一些特殊情况需要进行特殊处理。

以下是一个简单的 Java 贪心算法的实现示例，用于解决一种经典的问题：'找零钱'。

import java.util.*;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        int[] coins = {25, 10, 5, 1}; // 可用的硬币面值
        int money = 41; // 需要找的钱数
        List<Integer> change = makeChange(coins, money); // 执行贪心算法
        System.out.println(change); // 输出找零方案
    }

    public static List<Integer> makeChange(int[] coins, int money) {
        List<Integer> result = new ArrayList<>();
        int i = 0;
        while (money > 0) {
            if (money >= coins[i]) {
                money -= coins[i];
                result.add(coins[i]);
            } else {
                i++;
            }
        }
        return result;
    }
}

在上面的示例中，我们首先定义了一个硬币面值数组 coins 和需要找的钱数 money。然后，我们调用 makeChange 函数来执行贪心算法，该函数根据当前剩余的钱数 money 选择可用硬币中面值最大的硬币，并将其添加到结果列表中。

最后，我们输出找零方案，即结果列表。在这个例子中，找零方案为 [25, 10, 5, 1]，与我们预期的结果一致。