Java如何实现计算凑成指定金额所需的各面值纸币数量

实现思路 #

采用贪心算法实现，默认适配绝大多数常规面值体系，支持传入任意数量的面值参数、任意正整数目标金额，内部会自动对传入的面值做降序排序，无需提前手动调整顺序。如果是非规则面值需要严格保证最少纸币张数，可替换为下方的动态规划实现版本。

完整实现代码 #

import java.util.*;
import java.util.stream.Collectors;

public class BillCounter {
    // 贪心算法实现，适合常规面值体系，计算速度快
    public static Map<Integer, Integer> countBills(int[] bills, int targetAmount) {
        // 入参校验
        if (targetAmount < 0) {
            throw new IllegalArgumentException("目标金额不能为负数");
        }
        if (bills == null || bills.length == 0) {
            throw new IllegalArgumentException("面值数组不能为空");
        }
        // 面值数组降序排序并去重
        List<Integer> sortedBills = Arrays.stream(bills)
                .distinct()
                .boxed()
                .sorted(Collections.reverseOrder())
                .collect(Collectors.toList());
        Map<Integer, Integer> result = new LinkedHashMap<>();
        int remaining = targetAmount;

        for (int bill : sortedBills) {
            if (bill <= 0) {
                throw new IllegalArgumentException("面值不能为0或负数");
            }
            int count = remaining / bill;
            result.put(bill, count);
            remaining = remaining % bill;
        }

        // 剩余金额不为0说明当前面值组合无法凑出目标金额
        if (remaining != 0) {
            throw new IllegalArgumentException("当前面值组合无法凑出指定金额");
        }
        return result;
    }

    public static void main(String[] args) {
        // 示例测试
        int[] bills = {100,50,20,10,5,1};
        int target = 374;
        Map<Integer, Integer> countResult = countBills(bills, target);
        // 按示例格式输出
        int index = 1;
        for (Map.Entry<Integer, Integer> entry : countResult.entrySet()) {
            System.out.printf("Bill%d: %d、", index, entry.getValue());
            index++;
        }
    }
}

运行示例输出 #

输入面值[100,50,20,10,5,1]、目标金额374时，输出结果为：

Bill1: 3、Bill2: 1、Bill3: 1、Bill4: 0、Bill5: 0、Bill6: 4

特殊面值场景补充（动态规划版本，保证最少张数） #

如果你的使用场景存在非标准面值（例如[3,2]凑4元的场景，贪心算法会算出1张3+1张1，没有2张2的方案优），可以使用动态规划版本实现，代码如下：

// 动态规划实现，保证任意面值下凑出目标金额的纸币张数最少
public static Map<Integer, Integer> countBillsDp(int[] bills, int targetAmount) {
    if (targetAmount < 0) throw new IllegalArgumentException("目标金额不能为负数");
    if (bills == null || bills.length == 0) throw new IllegalArgumentException("面值数组不能为空");
    int[] dp = new int[targetAmount + 1];
    int[] prev = new int[targetAmount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE - 1);
    Arrays.fill(prev, -1);
    dp[0] = 0;

    for (int i = 1; i <= targetAmount; i++) {
        for (int bill : bills) {
            if (bill <= i && dp[i - bill] + 1 < dp[i]) {
                dp[i] = dp[i - bill] + 1;
                prev[i] = bill;
            }
        }
    }

    if (dp[targetAmount] == Integer.MAX_VALUE - 1) {
        throw new IllegalArgumentException("当前面值组合无法凑出指定金额");
    }

    Map<Integer, Integer> result = new HashMap<>();
    for (int bill : bills) {
        result.put(bill, 0);
    }
    int current = targetAmount;
    while (current > 0) {
        int bill = prev[current];
        result.put(bill, result.get(bill) + 1);
        current -= bill;
    }
    // 按面值降序排序返回
    return result.entrySet().stream()
            .sorted(Map.Entry.<Integer, Integer>comparingByKey().reversed())
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
}

内容的提问来源于stack exchange，提问作者Jacob Bennett