电影兑换券的推荐策略——二分图最优匹配算法

摘要

用户下了一笔订单，订单中有 x（根据业务场景，x <= 6）张电影票，y 张兑换券，从这 y 张兑换券中选择不超过 x 张兑换券，使得该笔订单的实际支付金额最少，如果有多种解决方案，那么根据以下优先级为用户推荐选券的方案：

• 优先级 1: 选择实际支付金额少的方案
• 优先级 2: 如果实际支付金额一致，则优先使用面值小的方案
  • 原因：如果用户想购买一张票价为 38 元的电影票，当前他有一张 40 元和一张 60 元的兑换券，任意使用一张兑换券能得到的实际支付金额都是 0 元，那么优先为用户选择 40 元的兑换券，这样 60 元的兑换券就能服务于用户的下一笔订单，更能为用户省钱。
• 优先级 3: 若面值大小也一致，则优先使用优惠券所在券包消耗券数目多的优惠券
• 优先级 4: 若消耗券数目一致，则优先使用过期时间早的优惠券