如何高效实现固定张数纸币的金额分配算法（Python）

问题背景 #

给定纸币面额列表（如[200, 100, 50, 20, 10, 5, 2]），要求分配出总张数固定、总金额固定的纸币组合，且每种纸币的数量至少为1张。原实现采用多层嵌套循环，不仅代码冗余，而且遍历范围无限制，效率极低；同时需要支持任意张数、金额的通用场景。

注：原示例中总张数512、总金额1397的组合实际无解，以下方案可通用判断并返回可行解（若存在）。

优化思路 #

• 转换约束条件：先为每种纸币预先分配1张，将问题转化为求解非负整数解的问题：
  • 剩余张数 = 总张数 - 面额种类数
  • 剩余金额 = 总金额 - 所有面额的总和
    若剩余张数或剩余金额为负，直接判定无解。
• 减少无效遍历：针对每个面额，计算其最大可能数量（受剩余金额、剩余张数限制），避免无意义的循环范围。
• 优先处理大面额：大面额的数量范围更小，优先遍历可大幅减少循环次数。

通用实现代码 #

def find_note_combination(total_notes, total_amount, denominations):
    n = len(denominations)
    # 先给每种纸币分配1张，转换问题
    required_notes = n
    required_amount = sum(denominations)
    
    # 检查初始条件是否可行
    if total_notes < required_notes or total_amount < required_amount:
        return None
    remaining_notes = total_notes - required_notes
    remaining_amount = total_amount - required_amount
    
    # 按面额从大到小排序，提升遍历效率
    sorted_denoms = sorted(denominations, reverse=True)
    # 存储每种面额的数量（最后还原原始顺序）
    counts = [1] * n
    
    def backtrack(index, rem_notes, rem_amount):
        if index == n - 1:
            # 处理最后一种面额，验证是否匹配剩余张数和金额
            if rem_amount % sorted_denoms[index] == 0 and rem_amount // sorted_denoms[index] == rem_notes:
                counts[denominations.index(sorted_denoms[index])] += rem_notes
                return True
            return False
        
        # 当前面额的最大可能数量：不超过剩余张数，也不超过剩余金额除以面额的商
        max_count = min(rem_notes, rem_amount // sorted_denoms[index])
        # 从最大可能数量往下遍历，找到解立即返回
        for cnt in range(max_count, -1, -1):
            counts[denominations.index(sorted_denoms[index])] += cnt
            if backtrack(index + 1, rem_notes - cnt, rem_amount - cnt * sorted_denoms[index]):
                return True
            counts[denominations.index(sorted_denoms[index])] -= cnt
        return False
    
    if backtrack(0, remaining_notes, remaining_amount):
        # 返回面额与数量的对应字典，直观展示结果
        return dict(zip(denominations, counts))
    else:
        return None

# 测试原示例（无解场景）
denoms = [200, 100, 50, 20, 10, 5, 2]
result = find_note_combination(512, 1397, denoms)
if result:
    for denom, count in result.items():
        print(f"面额{denom}的纸币数量：{count}")
else:
    print("无可行分配方案")

# 测试有解场景：总张数5，面额[3,2,1]，总金额10，每种至少1张
denoms_test = [3, 2, 1]
result_test = find_note_combination(5, 10, denoms_test)
if result_test:
    print("\n有解场景结果：")
    for denom, count in result_test.items():
        print(f"面额{denom}的纸币数量：{count}")
else:
    print("\n无可行分配方案")

代码说明 #

• 约束转换：预先分配每种纸币1张，将问题简化为非负整数解的寻找，减少了循环中的条件判断。
• 回溯剪枝：按面额从大到小遍历，每次计算当前面额的最大可能数量，从大到小尝试，找到解立即返回，避免无效遍历。
• 通用性：支持任意面额列表、总张数和总金额的输入，返回直观的面额-数量字典，无解时返回None。

内容的提问来源于stack exchange，提问作者Étalo Machado