记一次优惠券最优使用算法

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《记一次优惠券最优使用算法》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~

记一次优惠券最优使用算法

先说一下业务背景。公司做的一个投资的APP，投资金额可以用优惠券抵扣。红包面额（100，50，30，10）

优惠券使用规则：

• 优先使用大面额的红包，即优先使用张数最少的红包组合
• 优先使用有限制的红包，即优先使用有限制红包张数占比最大的组合
• 优先使用即将过期的红包，即优先使用平均有效期最短的组合
• 选择红包面额之和最大的组合（面额总值≤投资额*1%）

算法尝试

前面三个都可以通过数据库检索排序实现生成一个数组，最后一个就要使用程序算法实现了。
一开始有想过背包法、穷举法。

• 背包法：说实在的，没看懂（比较尴尬），实现是可以实现。但是无法获取具体使用了哪张优惠券(简单就是很难获得优惠券的Id)
• 穷举法：数据太多，不可控。

优惠券最优算法1.0

算出用户本次投资最大使用优惠券总额（amount）、获取用户的优惠券列表(couponList)（已按前三规则排序）直接上代码:

    /**
     * 红包最优算法
     */
    private function getBestCoupon($couponList, $amount)
    {
        $restAmount = $amount
        $couponIdList = []
        foreach ($coupon as $couponList) {
            if ($restAmount >= $coupon->amount) {
                $couponIdList[] = $coupon->id;
                $restAmount     = $restAmount - $coupon->amount;

                if ($restAmount == 0) break;
            }
        }

        return [$couponIdList, $amount - $restAmount];
    }

实例解析：用户投资9000，用户有优惠券（50，30，30，30，30）

• 用50块尝试，最多80
• 用第一个30尝试，最多90，已经最优，中断程序（否则继续向下类推）

问题

• 因为每次算完就把该红包从数组中推出，这样还是存在问题。例如投资1600，用户有（100，50，30，30）。这样就不会出现最优。
• 还有就是没有按照有效期使用顺序。例如投资 7000, 用户有（50，30，30，30，10）。这样就会用到后面三张，第一张 30 就没有用，这个可以通过推出同面额最后一张解决。

解决(算法2.0)

• 不把计算过优惠券推出，需要每次把要计算那张优惠券单独拿出来
• 这样程序复杂了很多，但还是可以实现的
• 这样还是会出现算法1.0的问题，不过这种按照顺序取优惠券很难不出现问题。但是这种面额的优惠券出现几率几乎没有

请教

• 期待有大神给出更好的算法

本篇关于《记一次优惠券最优使用算法》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于数据库的相关知识，请关注golang学习网公众号！