仅用$20和$50纸币的ATM取现最少纸币数正确算法问询

贪心算法在这种纸币组合下不适用——它只优先选择大面额，会出现无法凑齐目标金额或得到非最优解的情况，比如你给出的110和130的例子：贪心算法要么留下无法用20凑的余数，要么得到的总张数不是最少的。

下面是两种无需大量if语句的合理解法：

方法一：遍历验证法 #

从最多的50美元纸币数量开始向下遍历，找到第一个能让剩余金额被20整除的组合——因为总张数随50纸币数量的增加而减少，第一个符合条件的组合就是最优解。

def calculate_min_notes(amount):
    # 过滤无效金额：非10的倍数或小于20的金额
    if amount % 10 != 0 or amount < 20:
        return None
    
    max_fifties = amount // 50
    # 从最多的50纸币开始试，直到0
    for fifties in range(max_fifties, -1, -1):
        remainder = amount - fifties * 50
        if remainder % 20 == 0:
            twenties = remainder // 20
            return {50: fifties, 20: twenties}
    
    # 无法凑出的情况（如30美元）
    return None

测试示例：

print(calculate_min_notes(110))  # 输出 {50: 1, 20: 3}
print(calculate_min_notes(130))  # 输出 {50: 1, 20: 4}
print(calculate_min_notes(100))  # 输出 {50: 2, 20: 0}（最优解）
print(calculate_min_notes(70))   # 输出 {50: 1, 20: 1}（最优解）

方法二：数学推导法 #

通过数学公式直接计算最优解，无需遍历，效率更高：
设50美元数量为x，20美元数量为y，目标金额amount可转化为：
50x + 20y = amount → 两边除以10得 5x + 2y = total（total = amount // 10）
总张数x + y = (total - 3x)/2，要最小化总张数，需最大化x，且total -5x需为非负偶数（因为2y必须是偶数）。

def calculate_min_notes_math(amount):
    if amount % 10 != 0 or amount < 20:
        return None
    
    total = amount // 10
    max_fifties = total // 5
    fifties = max_fifties
    
    # 确保total和x同奇偶（因为5x的奇偶性等于x的奇偶性）
    if total % 2 != fifties % 2:
        fifties -= 1
        # 若减1后仍不满足，再减1（最多减2次，奇偶性必然匹配）
        if fifties >=0 and total %2 != fifties%2:
            fifties -=1
    
    # 检查是否为有效数量
    if fifties <0 or (total - 5*fifties) <0:
        return None
    
    twenties = (total -5*fifties) //2
    return {50: fifties, 20: twenties}

两种方法都能正确处理所有有效金额，逻辑简洁，避免了冗余的if判断。

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