Java贪心算法详解与找零钱案例实现

什么是贪心算法

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。其核心在于“局部最优”推导“全局最优”，而非像动态规划那样通过状态转移方程解决重叠子问题。

场景引入：找零钱问题

为了直观理解，我们以经典的找零钱问题为例。假设你是小卖店老板，拥有若干面值的零钱 c[0], c[1], ..., c[n-1]。顾客购买商品后需要找回总额为 total 的钱，要求使用的零钱张数最少，以便顾客携带方便。

第1步：确定问题模型

该问题的目标是求解使 sum(c_i) == total 的零钱数量最小值。这属于典型的求解极值（最值）问题，具备贪心选择的性质——即在每一步尽可能选取面值最大的零钱。

第2步：穷举法的困境

最基础的思路是列举所有能凑成 total 的组合，然后找出张数最少的一个。例如总金额为11，面值为 {1, 3, 5}，组合可以是 {5,5,1}, {5,3,3} 等。

然而，当总金额较大或面值种类较多时，组合数量呈指数级爆炸增长，穷举法计算复杂度极高，不具备实用性。

贪心策略的实现过程

贪心算法的思路更直接：既然要找张数最少，那就每次都挑当前能用的最大面值。假设面值足够充足且按从大到小排序：

1. 第一步：总需求11，最大面值5。取一张5，剩余需求 11 - 5 = 6。
2. 第二步：剩余6，最大面值仍为5。再取一张5，剩余需求 6 - 5 = 1。
3. 第三步：剩余1，最大可用面值变为1。取一张1，剩余需求 1 - 1 = 0。

最终结果为 1 + 1 + 1 = 3 张。这个过程体现了“每次局部最优”的思想。

第3步：Java代码实现

基于上述逻辑，我们可以编写如下Java代码来计算最小零钱张数。注意：代码假设输入的面值数组 values 是从大到小排列的。

/**
 * @Author: mufeng
 * @Date: 2022/5/15 15:33
 * @Version: V 1.0.0
 * @Description: 使用贪心算法计算满足条件的最小零钱张数
 */
public class MinChangeCountSolution {
    public static void main(String[] args) {
        // 示例面值：已按从大到小排序
        int values[] = {5, 5, 3, 3, 1}; 
        // 实际逻辑中values通常代表可选的面额种类，此处简化演示遍历逻辑
        // 若values表示可无限使用的单一币种列表，需调整逻辑
        // 这里演示标准贪心：给定面额数组{5,3,1}和需求11
        int[] denominations = {5, 3, 1};
        System.out.println(getMinChangeCount(11, denominations));
    }

    /**
     * 计算最小张数
     * @param total 需要找零的总数
     * @param values 从大到小排列的面值数组
     * @return 最小张数，无法组成则返回-1
     */
    static int getMinChangeCount(int total, int[] values) {
        int rest = total;
        int result = 0;
        int count = values.length;

        // 从大到小遍历所有面值
        for (int i = 0; i < count; ++i) {
            if (rest == 0) break;

            // 计算当前面值最多能用几张
            int needCount = rest / values[i];
            
            // 更新剩余金额
            rest -= needCount * values[i];
            
            // 累计张数
            result += needCount;
        }

        // 如果最后剩余金额不为0，说明无法由这些面值精确组成
        if (rest != 0) {
            return -1;
        }
        return result;
    }
}

在上述标准面值体系 {5, 3, 1} 下，代码对于 total=11 能正确输出 3。

贪心算法的局限性：陷入局部最优陷阱

贪心算法并非万能。它最大的弱点在于：做出的局部最优选择在长远来看可能导致全局非最优，甚至无解。这在数学上称为“贪心选择不具备最优子结构性质”。

案例分析：面值缺失的情况

考虑一种特殊情况：假设零钱只有面值为 5 和 3 的纸币，需要找零 11。

• 贪心策略执行：
  • 优先选5：11 - 5 = 6
  • 再选5：6 - 5 = 1
  • 剩余1：没有面值为1的硬币，也没有其他组合能凑出1（只能退回去换）。
  • 代码返回 -1，认为无解。
• 实际情况：
  • 存在合法解：3 + 3 + 5 = 11，共3张。
  • 但贪心算法因为一开始就贪心地取了两个5，导致后续无路可走，无法进行“回溯”来尝试之前的选择。

对比：为什么动态规划更稳妥？

此类涉及“多阶段决策”且当前最优不一定导致全局最优的问题，通常更适合使用动态规划（Dynamic Programming）。动态规划会记录所有可能的子状态（如金额1到11分别最少需要几张），确保不遗漏任何可行路径，从而找到真正的全局最优解。

总结

贪心算法以其简洁和高效率著称，适用于具有“贪心选择性”和“最优子结构性”的问题（如哈夫曼编码、Prim/Kruskal最小生成树等）。但在解决如通用找零钱问题时，必须警惕其因缺乏回溯能力而导致的失效风险。在实际开发中，若面临此类优化问题，建议先验证贪心策略的正确性，否则应考虑动态规划等更通用的解法。

以上就是Java贪心算法超详细讲解的详细内容，更多关于Java贪心算法的资料请关注本站其它相关文章！