优惠券方案设计
流程
对优惠券的下列需求：
- 判断一个优惠券是否可用，也就是检查订单金额是否达到优惠券使用门槛
- 按照优惠规则计算优惠金额，能够计算才能比较并找出最优方案
- 生成优惠券规则描述，目的是在页面直观的展示各种方案，供用户选择
惠券规则从类型来说就4种：
- 每满减：例如每满100减10
- 折扣：例如满100打9.5折，最大不超过50
- 无门槛：例如直接抵扣10元
- 满减：例如满100减15
另外，优惠券描述中基本都会包含下列字段：
- 优惠门槛（thresholdAmount）：也就是优惠的基本条件，例如满100
- 优惠值（discountValue）：也就是具体折扣，例如减10、打9.5折
- 最大优惠（maxDiscountValue）：最大折扣，限制折扣金额
对应的数据库表结构如下：
思路分析
简单来说，这就是一个查询优惠券、计算折扣、筛选最优解的过程。整体流程如下：
最终找出优惠券组合方案的最优解，需要满足：
- 用券相同时，优惠金额最高的方案
- 优惠金额相同时，用券最少的方案
大概步骤包括：
- 定义接口
- 查询用户的优惠券
- 初步筛选
- 细筛并完成全排列
- 计算优惠明细
- 基于CompleteableFuture做并行计算
- 筛选最优解
初筛
是基于所有课程计算总价，判断优惠券是否可用，这显然是不合适的。应该找出优惠券限定范围内的课程，然后计算总价，判断是否可用。
所以引入细筛
细筛
细筛步骤有两步：
- 首先要基于优惠券的限定范围对课程筛选，找出可用课程。如果没有可用课程，则优惠券不可用。
- 然后对可用课程计算总价，判断是否达到优惠门槛，没有达到门槛则优惠券不可用
优惠方案全排列
在完成优惠券细筛以后，我们就可以拿到所有的优惠券。由于优惠券的使用顺序不同，可能导致最终的优惠金额不同。
我们要找出优惠金额最高的优惠券组合，就必须先找出所有的排列组合，然后分别计算出优惠金额，然后对比并找出最优解。
这里我们采用的思路是这样的：
- 优惠券放在一个List集合中，他们的角标就是0~N的数字
- 找优惠券的全排列组合，就是找N个不重复数字的全排列组合
- 例如2个数字：[0,1]，排列就包含：[0,1]、[1,0]两种
- 然后按照角标排列优惠券即可
计算优惠明细
单张优惠券算法
单张优惠券的优惠金额计算流程如下：
- 1）判断优惠券限定范围，找出范围内的课程
- 2）计算课程总价
- 3）判断券是否可用
- 4）计算优惠金额
例如现在有一些商品：
然后有一张优惠券：
我们按照上述算法来判断：
- 1）判断限定范围：这张券限定分类 b，对应的商品序号是2、3
- 2）计算课程总价：商品序号2、3的总价为200
- 3）判断是否可用：总价刚好达到优惠券满减门槛200，可以使用
- 4）计算优惠：满200减100，因此最终优惠金额就是100元
券叠加算法
券叠加就是按照券组合的顺序，依次计算每张券的优惠金额，最终优惠金额就是所有权的优惠累加。
需要注意的是：由于一张券计算完优惠后，商品的金额会发生变化，因此下一张券的计算金额会随之改变，因此券叠加的顺序非常重要。
而且为了方便计算后续券的优惠金额，我们必须知道商品金额具体的变化，也就是弄清楚每一张优惠券使用后，每个商品的具体优惠金额，我们称之为优惠明细，我们可以用一个表格来记录：
因此，券叠加算法比单券算法需要多一步：
- 1）判断优惠券限定范围，找出范围内的课程
- 2）计算课程总价
- 3）判断券是否可用
- 4）计算优惠金额
- 5）计算优惠明细
例如现在有一些商品：
然后有一组优惠券：
最终的计算步骤如下：
券1的计算步骤如下：
- 1）判断范围：券1可用于所有分类，因此商品序号1、2、3都可以用
- 2）计算总价：所有商品累加共300元
- 3）判断是否可用：券1门槛是100，符合要求
- 4）计算优惠金额：每满100减20，因此总共折扣就是60元
- 5）计算优惠明细：
优惠明细的计算算法如下：
- 正常情况下，按照商品价格在商品总价中的比例，乘以优惠总金额
- 最后一个商品，为了避免出现精度损失导致的金额不一致，最后一个商品的优惠明细等于优惠总金额减去其它商品的优惠明细之和
例如，商品1、2的折扣：（100 / 300）* 60 = 20 ，商品3的折扣等于：60 - 20 - 20 = 20
券2的计算步骤如下：
- 1）判断范围：券2可用于分类b，因此商品序号2、3都可以用
- 2）计算总价：商品2已经优惠了20，现在价格是80，商品3已经优惠了20，现在价格是80。因此商品总价是160
- 3）判断是否可用：券2门槛是200，不符合要求，跳过
券3的计算步骤如下：
- 1）判断范围：券3可用于所有分类，因此商品序号1可以用
- 2）计算总价：商品1原价100元，已经优惠20，现价80元
- 3）判断是否可用：券3门槛是80，符合要求
- 4）计算优惠金额：满80减20，因此总共折扣就是20元
- 5）计算优惠明细：由于只有商品1可用，商品1优惠明细就是20元
所以说现在
- 先找到优惠券对应的课程
- 计算课程的总价 (原价-折扣明细)
- 判断是否可用 如果不可用则跳过这个券
- 如果可用则 计算优惠金额
- 更新计算明细 规则(不是最后一个商品 则判断当前价格在总价格的百分比 * 优惠金额) 如果是最后一个 则将剩余的只赋值 然后更新明细 用map key 课程id value 金额
CompleteableFuture并发计算
所以，为了提高计算效率，我们可以利用多线程并行计算。具体步骤如下：
- 定义一个线程池
- for循环将每个方案交给一个线程去任务执行
- 等待所有任务计算完毕，返回结果
这里的难点有两个：
- 1）线程任务是带返回值的任务
- 2）虽然是多线程运行，但是我们要等待所有线程都执行完毕后才返回结果
针对第二个点，我们可以利用 JUC包提供的工具 CountDownLatch来实现。
针对第一个点，我们则需要利用一个JDK1.8的新工具：CompletableFuture来实现。
筛选最优解
现在，我们计算出了成吨的优惠方案及其优惠金额，但是该如何从其中筛选出最优方案呢？最优方案的标准又是什么呢？
首先来看最优标准：
- 用券相同时，优惠金额最高的方案
- 优惠金额相同时，用券最少的方案
我们寻找最优解可以参考上述过程，不过略有差异，核心原因是：券组合有多种，因此最优解不止一个。因此我们不能用一个变量类记录最优解，而是用Map来记录，结构如下：
其中：
- 第一个Map用来记录用券相同时，优惠金额最高的方案；
- 第二个Map用来记录优惠金额相同时，用券最少的方案。
最终，两个Map的values的交集就是我们要找的最优解。
评论区