Python硬币组合判定函数问题：指定金额与硬币数可行性判断

需要实现一个Python函数，输入美元金额（如1.25）和硬币数量（如6），判断是否能用恰好指定数量的硬币（quarters=25美分、dimes=10美分、nickels=5美分、pennies=1美分）精确组成该金额。

示例 #

• 1.00美元+6枚硬币：返回True（3 quarters + 2 dimes + 1 nickel）
• 1.25美元+5枚硬币：返回True（5 quarters）
• 1.25美元+8枚硬币：返回True（3 quarters + 5 dimes）
• 1.25美元+7枚硬币：返回False

原代码的核心问题 #

你的代码存在三个关键错误：

1. 浮点精度误差：直接用float处理美元金额会导致计算偏差（比如0.1 * 5并不精确等于0.5），干扰金额匹配判断。
2. 贪心算法不适用：贪心逻辑是用来找最少硬币数的，而本题要求恰好指定数量的硬币，贪心无法覆盖所有可能的组合（比如1.25美元8枚硬币的组合，贪心不会尝试3个quarter+5个dime的搭配）。
3. 变量逻辑混乱：sofar和num的更新逻辑无依据，循环仅遍历一次硬币类型，没有回溯尝试不同数量的同面值硬币。

正确解决方案 #

核心思路是枚举所有可能的硬币数量组合，同时将金额转换为整数美分避免浮点误差：

1. 把美元金额转为整数美分（比如1.25美元→125美分），硬币数量转为整数。
2. 枚举所有可能的quarter数量q（范围0到min(总硬币数, 总美分//25)）。
3. 对每个q，枚举可能的dime数量d（范围0到min(剩余硬币数, (剩余美分)//10)）。
4. 对每个d，枚举可能的nickel数量n（范围0到min(剩余硬币数, (剩余美分)//5)）。
5. 计算剩余硬币数p = 总硬币数 - q - d - n，检查p非负且q*25 + d*10 + n*5 + p*1等于总美分，存在符合条件的组合则返回True。

修正后的代码 #

def can_make_amount(dollars, num_coins):
    # 转换为整数美分，彻底避免浮点精度问题
    total_cents = round(dollars * 100)
    num_coins = int(num_coins)
    
    # 枚举所有可能的quarter数量
    max_q = min(num_coins, total_cents // 25)
    for q in range(max_q + 1):
        remaining_cents = total_cents - q * 25
        remaining_coins = num_coins - q
        if remaining_coins < 0:
            continue
        
        # 枚举dime数量
        max_d = min(remaining_coins, remaining_cents // 10)
        for d in range(max_d + 1):
            remaining_cents_d = remaining_cents - d * 10
            remaining_coins_d = remaining_coins - d
            if remaining_coins_d < 0:
                continue
            
            # 枚举nickel数量
            max_n = min(remaining_coins_d, remaining_cents_d // 5)
            for n in range(max_n + 1):
                p = remaining_coins_d - n
                if p < 0:
                    continue
                if remaining_cents_d - n * 5 == p * 1:
                    return True
    return False

测试验证 #

print(can_make_amount(1.00, 6))   # True
print(can_make_amount(1.25, 5))   # True
print(can_make_amount(1.25, 8))   # True
print(can_make_amount(1.25, 7))   # False

所有测试用例均返回正确结果。

内容的提问来源于stack exchange，提问作者omer manofaly