寻找可计算商品列表最优优惠券组合应用方案的高效算法

算法思路优化 #

首先可以先做目标等价转换：总支付金额 = 所有商品原价总和 - 总优惠抵扣额，因此问题可以转化为最大化总抵扣金额，后续所有方案都围绕这个目标展开。

方案1：状态压缩动态规划（适合优惠券数量≤20的场景，可得到精确最优解） #

如果你的业务场景中单次结算涉及的优惠券总数量m在20以内，这个方案的效率远高于朴素递归：

• 时间复杂度：O(m * 2^m)，m=20时仅需要计算约2000万次，完全可以在毫秒级返回结果
• 实现逻辑：
  1. 先做预处理过滤废券：
     • 过滤适用商品总价低于满减门槛的优惠券，这类券永远无法使用
     • 过滤总抵扣额≤0的优惠券，使用后不会带来收益
     • 被其他优惠券完全覆盖的低效券也可以直接删除：如果优惠券c1的适用商品范围包含c2、所有商品的抵扣额都≥c2、满减门槛≤c2，c2永远不会被选用，直接删除
  2. DP状态定义：dp[mask] 表示使用mask对应二进制位标记的优惠券时，能拿到的最大抵扣额，mask每一位代表对应优惠券是否被使用
  3. 状态转移：每次新增一张未使用的优惠券，从所有未分配的商品中选出适用该券的商品凑单，满足满减门槛后将对应抵扣额加入总收益，标记商品为已分配即可

方案2：最小割/最大权闭合子图（适合优惠券数量≤1000的场景，可得到精确最优解） #

如果优惠券数量更大，可通过网络流建图得到多项式时间复杂度的精确解：

• 建图逻辑：
  1. 建立源点S、汇点T
  2. 每个优惠券对应一个节点，源点S向优惠券节点连边，边权为该优惠券能提供的最大总抵扣额（所有适用商品的抵扣额之和）
  3. 每个商品对应一个节点，商品节点向汇点T连边，边权为商品原价
  4. 每个优惠券节点向所有适用的商品节点连边，边权为无穷大
  5. 对每个优惠券节点额外增加满减门槛限制：将优惠券节点拆分为入节点和出节点，中间连边的权值设置为满减门槛，确保只有凑单商品总价≥门槛时，这条边才不会被割开
• 最终最大总抵扣额 = 所有优惠券的最大总抵扣额之和 - 最小割的容量，对应就能算出最低总支付金额

方案3：贪心算法（适合业务高并发场景，次优解，误差通常<2%） #

如果不需要100%最优解，只是要在几毫秒内返回接近最优的结果，直接用贪心即可：

1. 给所有优惠券计算性价比：性价比 = 该券最大可抵扣总金额 / 满减门槛，性价比越高优先级越高
2. 按照优先级从高到低遍历优惠券，每次将所有未分配的、适用该券的商品凑单：
   • 如果凑单总价≥满减门槛，就使用该券，将这些商品标记为已分配，累加对应抵扣额
   • 不满足门槛就跳过该券
3. 所有未分配的商品默认不使用优惠券
   这个方案的时间复杂度仅为O(m log m + n*m)，完全可以支撑高并发的结算页实时计算。

剪枝优化补充 #

如果你还是想用搜索类的方案，可以加这两个剪枝规则，效率会提升几个量级：

• 优先给商品分配抵扣额最高的可用优惠券，尽早拿到较高的总抵扣额作为基线
• 每次递归前先计算剩余所有商品的最大可能抵扣额之和，如果加上当前已拿到的抵扣额还不如已有的最优解，直接终止当前分支的搜索

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