Python付款发送/收款列表金额匹配算法优化与问题求助

现有代码核心问题排查 #

• 重复匹配已删除元素：itertools.combinations 生成的是迭代器，你在迭代过程中修改了 sent 列表，但迭代器内的组合是基于生成瞬间的 sent 列表快照，不会随列表修改更新，所以会出现已经删除的元素还出现在后续组合里的问题，也就是你遇到的99.05重复匹配的bug。
• 迭代效率低下：每次匹配到任意项就重置 ircvd 为0从头遍历rcvd列表，产生大量重复计算，且每次匹配都生成所有长度的组合，没有提前剪枝，浪费算力。
• 浮点数精度风险：如果金额是浮点型，直接用 == 比较可能出现精度误差，建议转成分单位的整数处理。

逻辑优化方案 #

紧急修复当前bug #

每次找到匹配组合后立刻跳出所有组合迭代，重新从rcvd第一项开始匹配，避免用旧的组合迭代器：

• 优先匹配单笔完全相等的项，再匹配多笔组合，大幅提升速度
• 增加组合剪枝逻辑，不用遍历所有长度的组合
• 统一转成整数计算，避免浮点误差

优化后的实现代码 #

from itertools import combinations

# 金额转成分单位整数，避免浮点比较误差
def to_cents(f):
    return int(round(f * 100))
# 转回元单位用于输出
def to_yuan(c):
    return round(c / 100, 2)

# 原始数据
rcvd_raw = [6.83,8.36,9.97,11.81,14.97,27.23,33.63,39.09,40.75,91.35,91.83,99.05,109.30,135.10,158.82,161.02,164.50,174.51,196.55,249.29,262.17,283.29,309.26,311.02,317.28,367.51,417.41,491.31,557.08,559.88,569.00,653.92,1046.27,1097.94,1122.31]
sent_raw = [9.60,9.97,10.17,12.43,14.97,15.23,17.28,18.11,20.22,20.43,22.55,22.77,25.67,27.23,29.40,30.47,33.63,39.09,40.05,42.85,44.86,53.11,66.67,70.70,91.35,91.83,91.94,93.71,96.99,99.05,106.86,116.99,124.35,131.56,146.24,158.82,161.02,182.62,196.55,254.19,262.70,276.87,309.74,332.99,386.99,472.01,547.48,630.38,630.95,653.92,984.45]

# 转换单位并排序：rcvd降序，sent升序
rcvd = sorted([to_cents(x) for x in rcvd_raw], reverse=True)
sent = sorted([to_cents(x) for x in sent_raw])

print(f"rcvd总数: {len(rcvd)}, 总金额: {to_yuan(sum(rcvd))}")
print(f"sent总数: {len(sent)}, 总金额: {to_yuan(sum(sent))}")

matched_pairs = []
has_match = True

while has_match and rcvd and sent:
    has_match = False
    # 优先匹配单笔，速度最快
    for r_idx, r in enumerate(rcvd):
        if r in sent:
            s_idx = sent.index(r)
            s_val = sent.pop(s_idx)
            rcvd.pop(r_idx)
            matched_pairs.append(([to_yuan(s_val)], to_yuan(r)))
            print(f"-------MATCHED: [{to_yuan(s_val)}]  as total: {to_yuan(r)}")
            has_match = True
            break
    if has_match:
        continue
    # 单笔没匹配到，再匹配多笔，组合长度从2开始
    max_comb_len = len(sent)
    for comb_len in range(2, max_comb_len + 1):
        # 剪枝：最小的comb_len个sent的和都大于当前最大的rcvd，不用继续找更长的组合
        if sum(sent[:comb_len]) > rcvd[0]:
            break
        # 遍历当前rcvd列表找匹配
        for r_idx, r in enumerate(rcvd):
            # 剪枝：最大的comb_len个sent的和都小于当前r，直接跳过这个r
            if sum(sent[-comb_len:]) < r:
                continue
            # 找和等于r的组合
            for comb in combinations(sent, comb_len):
                if sum(comb) == r:
                    # 匹配到，移除对应sent和rcvd项
                    for s in comb:
                        sent.remove(s)
                    rcvd.pop(r_idx)
                    matched_pairs.append(([to_yuan(s) for s in comb], to_yuan(r)))
                    print(f"-------MATCHED: {tuple(to_yuan(s) for s in comb)}  as total: {to_yuan(r)}")
                    has_match = True
                    break
            if has_match:
                break
        if has_match:
            break

# 输出最终结果
unmatched_rcvd = [to_yuan(x) for x in sorted(rcvd)]
unmatched_sent = [to_yuan(x) for x in sorted(sent)]
print("\n==================最终结果==================")
print(f"未匹配rcvd: {unmatched_rcvd}, 总金额: {round(sum(unmatched_rcvd),2)}")
print(f"未匹配sent: {unmatched_sent}, 总金额: {round(sum(unmatched_sent),2)}")

多解场景边界求解思路 #

如果需要求未匹配sent金额最小/最大的结果，可以用0-1背包思路实现：

• 最小未匹配sent金额：等价于从sent中选出若干项，总和恰好等于某几个rcvd项的总和，且选中的sent总和最大
• 最大未匹配sent金额：等价于从sent中选出若干项，总和恰好等于某几个rcvd项的总和，且选中的sent总和最小
  当前你的数据量不大，用动态规划实现完全可以在合理时间内跑通。

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