贪心算法

找零问题：

假设有固定面额的硬币，要找给顾客一定金额，如何使用最少的硬币数量？

贪心算法的基本步骤：

1.建立数学模型描述问题
2.把求解的问题分成若干个子问题
3.对每个子问题求解，得到子问题的局部最优解
4.把子问题的局部最优解合成原来问题的一个解

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class GreedyChange {
    // 贪心算法解决找零钱问题
    public static List<Integer> makeChange(int amount, List<Integer> denominations) {
        // 存储找零的硬币
        List<Integer> change = new ArrayList<>();
        
        // 1. 排序硬币面额（从大到小）
        Collections.sort(denominations, Collections.reverseOrder());
        
        // 2. 遍历每种面额的硬币
        for (int coin : denominations) {
            // 3. 贪心选择：尽可能使用当前最大面额的硬币
            while (amount >= coin) {
                change.add(coin);
                amount -= coin;
            }
            
            // 如果金额已减为0，退出循环
            if (amount == 0) {
                break;
            }
        }
        
        // 如果无法找零（金额不为0）
        if (amount != 0) {
            return null;
        }
        
        return change;
    }
    
    public static void main(String[] args) {
        // 硬币面额（例如：1, 5, 10, 25分）
        List<Integer> coins = Arrays.asList(1, 5, 10, 25);
        int amount = 37; // 需要找零的金额
        
        List<Integer> result = makeChange(amount, coins);
        
        if (result != null) {
            System.out.println("找零 " + amount + " 分需要的硬币：" + result);
            System.out.println("最少硬币数量：" + result.size());
        } else {
            System.out.println("无法用给定面额找零 " + amount + " 分");
        }
    }
}

代码解释：

首先将硬币面额按从大到小排序，这是贪心算法的关键
然后从最大面额的硬币开始，尽可能多地使用该面额
减去已使用的金额后，继续用下一个较小面额的硬币重复操作
直到金额减为 0 或无法继续找零