现金支付设备的付款金额建议 algo

2026-10-24支付阿杰

结论

这不是典型的 0/1 knapsack，更接近以下几类问题：

找零或硬币组合问题（coin change）
整数分拆（integer partition）
需要多个最优解时，则属于 k-best coin change

不过，只知道面额集合和应付金额，还无法判断顾客最可能交多少钱。需要先明确：

是否允许超额支付；
允许支付的最大金额；
顾客最多会交多少张纸币或硬币；
如何判断一个组合是否更可能出现。

如果没有这些限制，候选数量没有上限。例如应付 87，顾客理论上可以交 100、200、500，甚至更高的金额。

示例中的 {1, 2, 10, 20, 50, 100} 不含面额 5，所以 “4 张 20、1 张 5、1 张 2” 不是合法组合。如果实际存在 5 元面额，需要把 5 加入面额集合。

建模方式

设应付金额为 (D)，各面额为 (v_i)，顾客交付数量为 (c_i)。现金总额为：

[ P=\sum_i c_i v_i ]

它必须满足：

[ P \ge D ]

同时还要设置合理的上限：

[ P \le P_{\max} ]

每个候选组合可以按以下因素评分：

[ score = w_1(P-D)

w_2\sum_i c_i
w_3\cdot complexity(c) ]

其中：

(P-D)：找零金额，通常越小越好；
(\sum_i c_i)：现金张数，通常越少越好；
complexity(c)：组合是否符合用户习惯；
(w_1,w_2,w_3)：业务权重。

顾客一般会优先考虑：

恰好支付；
支付 90、100 之类的整数金额；
少用几张现金；
使用常见的大面额；
避免支付明显过高的金额。

因此，“5 张 100” 虽然在数学上有效，但应付金额为 87 时，通常不该排在前几名。除非设备已经知道顾客实际拿出了多张 100。

推荐的两阶段算法

第一步：生成有限的候选支付总额

不必搜索所有大于应付金额的数值，只生成业务上合理的目标金额。例如应付 87 时，可以考虑：

精确金额：87；
按常用粒度取整：88、90、100；
如果有输入信号，再加入顾客实际拿出的金额。

可以用下面的方法生成候选总额：

def candidate_totals(due, denominations, max_overpay=100):
    totals = {due}

    for unit in denominations:
        rounded = ((due + unit - 1) // unit) * unit
        if rounded <= due + max_overpay:
            totals.add(rounded)

    return sorted(totals)

对于 due = 87 和 {1, 2, 10, 20, 50, 100}，结果类似：

87, 88, 90, 100

候选总额的生成规则应根据实际货币和用户行为调整，不能只依赖数学组合。

第二步：为每个总额求 top k 个现金组合

下面的动态规划会为指定金额保留现金张数最少的前 k 个组合。组合用计数元组表示，因此不同排列不会被当成不同答案。

from dataclasses import dataclass


@dataclass(frozen=True)
class PaymentOption:
    total: int
    change: int
    pieces: int
    counts: tuple


def top_k_exact_combinations(target, denominations, k):
    """
    返回恰好组成 target 的前 k 个组合。
    默认按现金张数从少到多排序。
    """
    denominations = tuple(sorted(set(denominations)))

    # dp[amount] 保存当前前 k 个组合
    dp = [[] for _ in range(target + 1)]
    dp[0] = [tuple(0 for _ in denominations)]

    for coin_index, coin in enumerate(denominations):
        for amount in range(coin, target + 1):
            candidates = list(dp[amount])

            for previous in dp[amount - coin]:
                counts = list(previous)
                counts[coin_index] += 1
                candidates.append(tuple(counts))

            # 去重，并按张数、组合计数作稳定排序
            candidates = sorted(
                set(candidates),
                key=lambda counts: (sum(counts), counts)
            )

            dp[amount] = candidates[:k]

    return dp[target]

再把多个候选支付总额对应的组合放在一起评分：

def recommend_payments(
    due,
    denominations,
    top_x=6,
    max_overpay=100,
    combinations_per_total=6,
):
    totals = candidate_totals(
        due,
        denominations,
        max_overpay=max_overpay,
    )

    options = []

    for total in totals:
        combinations = top_k_exact_combinations(
            total,
            denominations,
            combinations_per_total,
        )

        for counts in combinations:
            options.append(
                PaymentOption(
                    total=total,
                    change=total - due,
                    pieces=sum(counts),
                    counts=counts,
                )
            )

    # 示例排序：
    # 1. 找零更少
    # 2. 张数更少
    # 3. 支付总额更小
    options.sort(
        key=lambda option: (
            option.change,
            option.pieces,
            option.total,
        )
    )

    return options[:top_x]

使用示例：

denominations = [1, 2, 10, 20, 50, 100]

results = recommend_payments(
    due=87,
    denominations=denominations,
    top_x=6,
)

for option in results:
    combination = {
        denomination: count
        for denomination, count in zip(
            denominations,
            option.counts,
        )
        if count > 0
    }

    print(
        f"支付 {option.total}，"
        f"找零 {option.change}，"
        f"共 {option.pieces} 张/枚："
        f"{combination}"
    )

“最可能”不能只按找零金额排序

如果只按找零金额从少到多排序，所有精确支付 87 的组合都会排在支付 90 或 100 的组合之前。但在现实中，顾客可能更愿意交一张 100，而不是凑出很多零钱。

可以使用加权评分：

def payment_score(option):
    return (
        option.change * 1.0
        + option.pieces * 3.0
    )

也可以使用分层排序：

def payment_rank(option):
    exact_payment = option.change == 0
    round_total = option.total % 10 == 0

    return (
        0 if exact_payment else 1,
        0 if round_total else 1,
        option.pieces,
        option.change,
    )

哪种方式更合理，需要用真实交易数据验证。如果有历史数据，可以统计：

[ P(\text{组合}\mid \text{应付金额、地区、时间、设备类型}) ]

然后直接按预测概率排序。动态规划用于生成候选，行为模型用于排序。这样通常比让一个纯组合算法同时解决两个问题更可靠。

如果现金数量有限

如果设备知道顾客或收银员实际提供了哪些现金，例如最多有：

available = {
    1: 3,
    2: 2,
    10: 1,
    20: 4,
    50: 0,
    100: 1,
}

这时问题就变成 bounded coin change，也就是每种面额都有数量上限。动态规划状态需要满足：

[ 0 \le c_i \le available_i ]

如果每张现金只能使用一次，也可以将它看作 0/1 knapsack 的变体。原题没有给出数量限制，因此更适合按现金数量无限的 coin change 建模。

性能与实现注意事项

上述动态规划适合支付金额较小、面额种类较少的收银场景。大致开销取决于：

[ O(d \times P_{\max} \times k) ]

实际的去重和排序还会带来额外开销，不过 d 和 k 通常都很小。

实现时还要注意：

金额应使用最小货币单位的整数，例如 “分”，不要使用浮点数；
必须限制最大超额支付金额，否则搜索空间没有上界；
相同现金数量的不同排列应视为同一个组合；
如果每种面额有库存限制，应改用 bounded coin change；
必须明确 top x 的含义，是 “最少找零”、“最少张数” 还是 “最高行为概率”；
如果评分函数较复杂，而且候选金额很大，可以使用优先队列、A* 或 k-shortest-path 方法按评分逐个生成结果，避免枚举全部组合。

核心算法可以采用 k-best coin change 动态规划，但最终的推荐质量主要取决于候选范围和排序规则，而不是 knapsack 算法本身。