Python3：从有限 pocket 中选择硬币并最小化找零

2026-10-24支付小周

结论

这个问题不适合用简单的贪心算法。每种硬币的数量有限，而且需要按顺序满足两个条件：先让支付金额尽可能小，再在支付金额相同时使用尽可能多的硬币。因此，这实际上是一个有限背包问题。

可以用动态规划保存每个可支付金额对应的最佳硬币组合：

找到不小于 amount 的最小可支付金额。
支付金额相同时，保留硬币数量最多的组合。
计算过程全部使用整数便士，最后再将找零转换为英镑。

实现代码

from decimal import Decimal


COIN_VALUES = [200, 100, 50, 20, 10, 5, 2, 1]


def pay_with_coins_from_pocket(amount, pocket):
    if len(pocket) != len(COIN_VALUES):
        raise ValueError("pocket 必须包含 8 个整数")

    if any(not isinstance(count, int) or count < 0 for count in pocket):
        raise ValueError("硬币数量必须是非负整数")

    decimal_amount = Decimal(str(amount))

    if decimal_amount < 0:
        raise ValueError("amount 不能为负数")

    pennies = decimal_amount * 100

    if pennies != pennies.to_integral_value():
        raise ValueError("amount 最多只能包含两位小数")

    target = int(pennies)
    total = sum(value * count for value, count in zip(COIN_VALUES, pocket))

    if total < target:
        raise ValueError("pocket 中的总金额不足")

    # 最小的超额支付不会达到 target + 最大硬币面值。
    upper_bound = min(total, target + max(COIN_VALUES) - 1)

    # dp[sum] = (硬币总数, 各面值硬币的使用数量)
    dp = {
        0: (0, (0,) * len(COIN_VALUES))
    }

    for index, (value, available) in enumerate(zip(COIN_VALUES, pocket)):
        next_dp = {}

        for current_sum, (coin_count, combination) in dp.items():
            max_usable = min(
                available,
                (upper_bound - current_sum) // value
            )

            for used in range(max_usable + 1):
                new_sum = current_sum + used * value
                new_coin_count = coin_count + used

                new_combination = list(combination)
                new_combination[index] = used
                new_combination = tuple(new_combination)

                previous = next_dp.get(new_sum)

                if previous is None or new_coin_count > previous[0]:
                    next_dp[new_sum] = (
                        new_coin_count,
                        new_combination
                    )

        dp = next_dp

    payable_amounts = [
        paid for paid in dp
        if paid >= target
    ]

    if not payable_amounts:
        # 按照前面的总额检查，正常情况下不会执行到这里。
        raise ValueError("找不到能够覆盖 amount 的硬币组合")

    paid = min(payable_amounts)
    combination = list(dp[paid][1])
    change = float(Decimal(paid - target) / Decimal(100))

    return combination + [change]

使用示例

假设只有一枚 2 英镑硬币，需要支付 1.62 英镑：

result = pay_with_coins_from_pocket(
    1.62,
    [1, 0, 0, 0, 0, 0, 0, 0]
)

print(result)

结果是：

[1, 0, 0, 0, 0, 0, 0, 0, 0.38]

函数会使用一枚 2 英镑硬币，并找回 0.38 英镑。

如果能够精确支付，函数会优先选择精确支付。例如：

result = pay_with_coins_from_pocket(
    1.62,
    [1, 1, 1, 1, 1, 1, 1, 2]
)

print(result)

返回组合的总额一定是 1.62 英镑，最后一个元素是：

0.0

如果多个组合的支付金额相同，动态规划会保留使用硬币最多的那个组合。

原算法为什么会失败

原代码按面值逐个处理硬币，并不断修改 amount：

amount = values_of_coins[i] - amount

执行这行代码后，amount 表示的不再是最初要支付的金额，而是当前差额。后续选择硬币时，也就无法判断整个组合实际支付了多少钱。

按面值依次选择硬币本身也是一种贪心策略。对于数量不限的硬币和某些特定面值体系，贪心策略可能有效。但这里不仅限制了每种硬币的数量，还要处理超额支付，并满足”支付金额相同时使用最多硬币”的规则，所以贪心算法无法保证结果正确。

原代码中的这一行还存在计数错误：

number_of_coins[i] = number_of_coins_used

number_of_coins_used 记录的是所有面值累计使用的硬币数，并不是当前面值使用的数量。即使改为递增当前位置，也无法解决硬币组合的选择问题。

注意事项

货币计算不应直接依赖二进制浮点数。例如：

amount * 100

某些金额经过计算后可能变成类似 161.999999999 的结果。代码先执行：

Decimal(str(amount))

这样可以将金额可靠地转换为整数便士，避免浮点误差。

当 pocket 中的总金额不足时，这段代码会抛出 ValueError。如果调用方约定用 None 或其他特殊值表示余额不足，可以把相应的异常处理改为：

return None

不建议返回一个看似正常的 9 元素列表，否则调用方很难区分”余额不足”和”支付成功但需要找零”。