如何确定给定价格下“常见”的现金付款金额
结论
仅凭流通面额，无法唯一判断哪种付款金额”最可能”出现。面额集合只能用来判断某个金额 P 能否组成。要对候选付款金额排序，还需要建立顾客行为模型，考虑以下因素：
- 顾客实际持有的硬币和纸币；
- 顾客是否倾向于少拿几张钱；
- 顾客是否偏爱
$5、$10、$20等整额； - 顾客是否希望减少找零；
- 顾客是否愿意使用多张相同纸币；
- 顾客是否会通过组合付款消耗零钱。
一种通用的实现方法是：
- 用整数形式的最小货币单位表示金额；
- 通过枚举或动态规划生成所有满足
P >= A的付款组合； - 计算每个组合的行为得分；
- 合并付款总额相同的组合；
- 按合并后的概率或得分排序。
这里需要特别注意：付款组合和付款总额是两个不同的概念，必须分别建模。8 × $20 与 $100 + 3 × $20 是两个不同的付款组合，但对应的候选付款金额都是 $160。
为什么不存在只依赖面额的标准答案
假设账单金额为 $22.65，支付 $25、$30 或 $40 都符合面额规则。哪一种更常见，取决于顾客钱包里有什么：
- 如果有一张
$20和一张$5，通常会付$25； - 如果没有
$5，但有$10，可能会付$30； - 如果只有两张
$20，就只能付$40； - 如果硬币足够，也可能支付一个非常接近账单的金额。
所以，这既不是单纯的找零问题，也不是经典的”最少硬币数”问题。经典零钱兑换算法解决的是：
如何用给定面额组成某个确定金额？
这里要解决的则是：
顾客可能选择哪些组合，这些组合在人类付款行为中出现的概率有多大？
没有钱包库存或真实交易数据时，算法只能根据明确的假设给出启发式排名，不能把结果称为准确概率。
建模方法
设面额为：
[ D={d_1,d_2,\ldots,d_n} ]
一个付款组合可以表示为：
[ x=(x_1,x_2,\ldots,x_n) ]
其中，x_i 表示面额 d_i 的使用数量。付款总额为：
[ P(x)=\sum_{i=1}^{n}d_i x_i ]
只保留满足以下条件的组合：
[ A \le P(x) \le A+L ]
L 表示允许的最大超付金额。这个上限是必需的，否则纸币数量不受限制时，候选组合会有无限多个。
可以为每个组合定义成本：
[ C(x,A)= \alpha N(x) +\beta K(P(x)-A) +\gamma R(P(x),A) +\delta T(x) ]
各项含义如下：
N(x)：顾客拿出的硬币和纸币总数；K(P-A)：收银员找零所需的最少张数或枚数；R(P,A)：超付金额惩罚；T(x)：使用的不同面额种类数；α、β、γ、δ：需要根据经验或交易数据校准的权重。
组合的相对权重可以定义为：
[ W(x\mid A)=e^{-C(x,A)} ]
同一个付款金额可能来自多个组合，因此，金额 P 的总权重应为：
[ W(P\mid A)=\sum_{x
(x)=P}W(x\mid A) ]最后按照 W(P | A) 从高到低排序。
这样合并既保留了面额组合逻辑，也不会把对应同一付款金额的不同组合当成多个候选金额。
一个可运行的 Python 示例
下面的实现以”分”为单位，避免浮点数误差。程序会枚举有限范围内的付款组合，再按照启发式行为模型聚合并排序。
from collections import defaultdict
from math import exp, inf
def min_pieces(amount, denominations):
"""计算组成 amount 所需的最少张数/枚数。"""
if amount == 0:
return 0
dp = [inf] * (amount + 1)
dp[0] = 0
for value in range(1, amount + 1):
for denomination in denominations:
if denomination <= value:
dp[value] = min(
dp[value],
dp[value - denomination] + 1
)
return dp[amount]
def common_payments(
amount,
denominations,
max_overpay,
max_counts=None,
limit=10,
alpha=1.0,
beta=0.35,
gamma=0.02,
delta=0.15,
):
"""
amount、denominations、max_overpay 均使用最小货币单位。
max_counts:
每种面额最多可使用多少张/枚。
如果为 None，则根据最大候选付款金额自动设置理论上限。
"""
denominations = sorted(set(denominations), reverse=True)
max_payment = amount + max_overpay
if max_counts is None:
max_counts = [
max_payment // denomination
for denomination in denominations
]
if len(max_counts) != len(denominations):
raise ValueError("max_counts 必须与 denominations 等长")
weights_by_payment = defaultdict(float)
best_combinations = {}
def visit(index, payment, counts, piece_count, type_count):
if payment > max_payment:
return
if index == len(denominations):
if payment < amount:
return
change = payment - amount
change_pieces = min_pieces(change, denominations)
# 如果零钱无法由给定面额组成，可选择排除该候选。
if change_pieces == inf:
return
overpay_units = change / min(denominations)
cost = (
alpha * piece_count
+ beta * change_pieces
+ gamma * overpay_units
+ delta * type_count
)
weight = exp(-cost)
weights_by_payment[payment] += weight
previous = best_combinations.get(payment)
if previous is None or cost < previous[0]:
best_combinations[payment] = (cost, tuple(counts))
return
denomination = denominations[index]
maximum = min(
max_counts[index],
(max_payment - payment) // denomination
)
for count in range(maximum + 1):
counts.append(count)
visit(
index + 1,
payment + count * denomination,
counts,
piece_count + count,
type_count + (1 if count else 0),
)
counts.pop()
visit(0, 0, [], 0, 0)
ranked = sorted(
weights_by_payment,
key=lambda payment: (
-weights_by_payment[payment],
payment
)
)
results = []
for payment in ranked[:limit]:
_, counts = best_combinations[payment]
combination = {
denomination: count
for denomination, count in zip(denominations, counts)
if count
}
results.append({
"payment": payment,
"change": payment - amount,
"weight": weights_by_payment[payment],
"representative_combination": combination,
})
return results调用示例：
denominations = [
10000, # $100
5000, # $50
2000, # $20
1000, # $10
500, # $5
25, # 25c
10, # 10c
5, # 5c
]
results = common_payments(
amount=2265, # $22.65
denominations=denominations,
max_overpay=4000, # 最多考虑多付 $40
limit=10,
)
for result in results:
print(result)这些权重只适合用来排序。如果需要将其归一化为候选集合内的概率，可以这样处理：
total_weight = sum(item["weight"] for item in results)
for item in results:
item["probability"] = item["weight"] / total_weight计算结果是模型概率，并不是经过现实数据验证的付款概率。
有钱包库存时的改进
如果知道顾客当前持有的现金，可以将 max_counts 设为实际库存。例如：
# denominations 已按从大到小排列
max_counts = [
1, # $100
1, # $50
3, # $20
0, # $10
1, # $5
4, # 25c
2, # 10c
1, # 5c
]
results = common_payments(
amount=15124,
denominations=denominations,
max_overpay=5000,
max_counts=max_counts,
)加入实际库存后，算法不会再假设顾客拥有任意数量的纸币，因此排名更有参考价值。
如果不知道具体库存，但掌握各种面额的持有概率，可以把库存概率加入组合权重：
[ W(x\mid A)
\Pr(\text{钱包包含 }x) \cdot e^{-C(x,A)} ]
面额持有概率可以根据历史付款数据估计。在实际系统中，付款金额分布、面额持有分布和消费场景通常比手工设置的权重更有影响。
动态规划与枚举如何选择
面额较少、付款上限较低，而且每种面额数量有限时，深度优先枚举比较容易实现，也能保留完整的组合信息。
金额范围较大时，可以考虑以下方法：
- 动态规划：按金额保存最佳组合或累计概率；
k最短路径：把”加入一张纸币”作为状态转移；- 束搜索：每一层只保留得分最高的一批组合；
- 整数规划：在复杂库存和行为约束下寻找最佳组合；
- 蒙特卡洛模拟：先生成钱包库存，再模拟顾客的付款选择。
如果只需要每个 P 对应的最佳组合，可以使用最小成本动态规划。如果要计算 W(P | A)，就必须累计所有相关组合的概率质量，不能只保存最优组合。
注意事项
1. 不要使用浮点数表示货币
应使用整数形式的分、厘或系统规定的最小货币单位。否则，$0.10 + $0.20 之类的运算可能出现二进制浮点误差。
2. 区分付款可行性与找零可行性
顾客能够用自己的面额组成 P，不代表收银员一定能用现有面额组成 P-A。实际模型最好分别提供：
- 顾客可以使用的面额与库存；
- 收银台可以用于找零的面额与库存。
不能默认两者完全相同。
3. 处理无法精确找零的价格
示例中的最小面额为 5c，但 $151.24 不是 5c 的整数倍。如果没有 1c 面额，也不允许使用其他支付方式，收银员就无法精确找零。
这时需要明确业务规则，例如：
- 将现金账单四舍五入到最近的
5c； - 实际还存在
1c面额； - 允许收银台使用题目中未列出的面额；
- 不要求找零金额能由给定面额集合精确组成。
算法不能自行猜测采用哪一条规则。
4. “少付几张”不一定意味着更常见
如果只追求最少的付款张数，$100 可能会在许多小额消费中排在前面，这通常不符合现实。评分时需要同时考虑超付金额、找零数量、钱包库存和整额偏好。
5. 组合数量可能迅速增长
即使面额种类不多，只要允许无限量使用纸币，搜索空间就是无限的。因此，至少需要限制以下一项：
- 最大付款金额；
- 最大超付金额；
- 每种面额的最大数量；
- 最大付款张数；
- 只保留前
k个候选状态。
6. 真正的”准确排序”需要数据
如果目标是预测真实顾客的付款行为，应使用历史交易记录拟合模型，例如条件概率：
[ \Pr(P\mid A,\text{场景},\text{钱包特征}) ]
可用特征包括账单金额、时段、国家或地区、现金舍入规则、付款张数、找零张数和面额组合。没有这些数据时，排名只能是合理的启发式结果，不能视为由面额集合推导出的客观答案。
备注：内容仅供参考。