凑单凑到一半，发现还是多花了钱
大促凑单最让人抓狂的时刻，不是凑不齐门槛，而是凑齐了却多花了不该花的钱。为了凑满300减50，硬塞了一件99元的商品，结果实付反而比不凑还贵——这是典型的"凑单最优解"没找到。
所谓凑单最优解，就是在满足满减门槛的前提下，找到总价最接近门槛（或实付金额最小）的商品组合。这篇文章用动态规划的思路，把凑单从"凭感觉挑"变成"按算法算"，并给出可直接套用的代码和数值案例。想先了解凑单的基本逻辑，可以看什么是凑单；想看基础凑单算法的朋友，推荐跨店满减最优凑单算法。
凑单问题建模：先把它变成一道数学题
任何算法题的第一步都是建模。凑单问题可以抽象成这样一个数学模型：
输入：一组商品价格 prices = [p1, p2, ..., pn]，满减规则"满 M 减 D"。
目标：选择若干商品组成子集 S，使得：
- 总价
sum(S) >= M（满足满减门槛） - 实付
sum(S) - D最小（等价于总价最接近门槛）
约束：每个商品最多选一次（01背包性质），不能拆单、不能凑单后退货（那是另一套玩法，见凑单退款规则）。
| 变量 | 含义 | 示例 |
|---|---|---|
| M | 满减门槛 | 300 |
| D | 减免金额 | 50 |
| sum(S) | 组合总价 | 306.9 |
| 超出额 | sum(S) - M | 6.9 |
| 实付 | sum(S) - D | 256.9 |
注意一个关键点："总价最接近门槛"和"实付最小"只有在满减档位唯一时等价。如果存在多档满减（比如满200减30、满300减50），两档可能同时满足，这时候要按实付比大小，而不是单纯看超出额。
动态规划思路：状态定义与转移方程
为什么不用穷举？8件商品有 2^8=256 种组合，30件商品就是 2^30 ≈ 10亿种，穷举不现实。动态规划（Dynamic Programming）的核心思想是把大问题拆成小问题，用一张表记录中间结果，避免重复计算。
状态定义
dp[j] 表示能否用若干商品凑出金额 j（布尔值，True 表示可以）。
转移方程
对每个商品价格 p，倒序遍历所有金额：
dp[j] = dp[j] or dp[j - p] （当 j >= p 时）
意思是：凑出金额 j，要么不选当前商品（dp[j] 保持原值），要么选了当前商品后，剩下的 j - p 能由之前的商品凑出（dp[j - p] 为 True）。
倒序遍历是关键——保证每个商品只被使用一次（01背包标准写法）。
代码实现
# 金额统一乘10转成整数，避免浮点误差
prices = [299, 499, 599, 890, 690, 990, 790, 399] # 单位：0.1元
target = 3000 # 满300减50
dp = [False] * (sum(prices) + 1)
dp[0] = True # 什么都不买，金额为0
for p in prices:
for j in range(sum(prices), p - 1, -1):
if dp[j - p]:
dp[j] = True
# 从门槛开始找第一个可达金额
for total in range(target, sum(prices) + 1):
if dp[total]:
print(f"最优凑单金额: {total / 10:.1f} 元")
print(f"实付: {total / 10 - 50:.1f} 元（减免50元）")
break
这个算法的时间复杂度是 O(n × Σprices)，n 是商品数，Σprices 是总金额——对于几十件商品的购物车，计算量在几万到几十万级别，瞬间出结果。
实际案例：满300减50的最优组合推演
我们用一组真实的日用品价格来验证。假设购物车里有这8件商品：
| 编号 | 商品 | 价格(元) |
|---|---|---|
| A | 抽纸 24包 | 29.9 |
| B | 洗衣液 4kg | 49.9 |
| C | 洗发水 750ml | 59.9 |
| D | 零食大礼包 | 89.0 |
| E | 保温杯 | 69.0 |
| F | 大米 10kg | 99.0 |
| G | 牛奶 24盒 | 79.0 |
| H | 厨房湿巾 | 39.9 |
促销规则：满300减50。我们对比三种策略：
策略一：贪心法（从贵到便宜硬凑）
按价格从高到低加：F(99) + D(89) + G(79) = 267，不够；再加 B(49.9) = 316.9。
- 组合：F+D+G+B
- 总价：316.9 元
- 实付：266.9 元，超出门槛 16.9 元
策略二：动态规划
用上面的代码跑一遍，从 3000（即300元）往上找第一个可达金额——结果是 306.9，对应组合 F+D+E+B（99+89+69+49.9）。
- 组合：F+D+E+B
- 总价：306.9 元
- 实付：256.9 元，超出门槛仅 6.9 元
结果对比
| 策略 | 组合 | 总价 | 实付 | 超出额 |
|---|---|---|---|---|
| 贪心法 | F+D+G+B | 316.9 | 266.9 | 16.9 |
| 动态规划 | F+D+E+B | 306.9 | 256.9 | 6.9 |
| 差异 | — | 10.0 | 省10元 | 10.0 |
同样的满减门槛，动态规划比贪心法省了10元。贪心法的毛病在于"先挑贵的"容易在最后一两步用力过猛，而动态规划会系统性地搜索所有可能，找到恰好压线的那一组。当然，本例商品只有8件，人工也能试出来；但当购物车里有30件商品、涉及多档满减时，人工枚举就完全无能为力了。
动态规划的进阶应用：多档满减与多券叠加
基础版动态规划解决"单档满减"，实际大促场景往往更复杂：
场景一：多档满减
比如"满200减30 / 满300减50 / 满500减100"。做法是分别对每个档位跑一次动态规划，得到各档最优实付，再取最小值：
| 档位 | 最优组合总价 | 减免 | 实付 |
|---|---|---|---|
| 满200减30 | 209.9 | 30 | 179.9 |
| 满300减50 | 306.9 | 50 | 256.9 |
| 满500减100 | 506.9 | 100 | 406.9 |
注意：满200减30的实付179.9元最低，但这是因为我们凑的是同一批商品的子集。真实场景中，如果凑单商品正好跨越多个门槛，要逐一比较实付，而不是无脑往高门槛冲——很多人的凑单预算就是这么超的。
场景二：叠加优惠券
动态规划同样可以处理"品类券+满减"的叠加。思路是分阶段：先算满减后的实付，再判断商品是否满足品类券门槛，套用满减叠加限制里的顺序规则逐步计算。更复杂的满减+折扣+红包三重叠加，可以参考三重叠加数学模型。
总结：什么时候该用动态规划凑单
回到开头的问题——凑单最优解不一定要每次都用程序算，但理解动态规划的思路，能让你在购物时做出更理性的判断：
- 商品多、门槛高时必算：购物车30件商品、满500减100这种场景，凭感觉凑大概率多花20元以上，值得用算法跑一遍。
- 贪心优先、DP兜底：商品少（5件以内）时人工挑"最接近门槛的组合"通常够用；商品一多，直接套用本文的动态规划代码。
- 多档满减比实付，不比门槛：哪个档位实付最低选哪个，别被"满500减100"的大数字吸引。
最后提醒：凑单前先确认商品是否参加满减、是否能用券，避免凑完发现某件商品不参与活动。日常购物懒得自己写代码的，可以直接用站内的凑单计算器快速算出最优组合，原理和本文的动态规划一致。
动态规划凑单的核心就三句话：状态定义要清晰、转移方程要正确、倒序遍历防重复。记住这三条，你也能成为凑单算法大师。