记一次优惠券最优使用算法
记一次优惠券最优使用算法
先说一下业务背景。公司做的一个投资的APP,投资金额可以用优惠券抵扣。红包面额(100,50,30,10)
优惠券使用规则:
优先使用大面额的红包,即优先使用张数最少的红包组合
优先使用有限制的红包,即优先使用有限制红包张数占比最大的组合
优先使用即将过期的红包,即优先使用平均有效期最短的组合
选择红包面额之和最大的组合(面额总值≤投资额*1%)
算法尝试
前面三个都可以通过数据库检索排序实现生成一个数组,最后一个就要使用程序算法实现了。
一开始有想过背包法、穷举法。
背包法:说实在的,没看懂(比较尴尬),实现是可以实现。但是无法获取具体使用了哪张优惠券(简单就是很难获得优惠券的Id)
穷举法:数据太多,不可控。
优惠券最优算法1.0
算出用户本次投资最大使用优惠券总额(redAmount)、获取用户的优惠券列表(redCoupons)(已按前三规则排序)直接上代码:
public function dealCoupon() { $redCoupons =[]; $restRedAmount = 100; $redCouponIdLists = []; $restRedAmounts = []; $arrCount = count($redCoupons); for ($i=0; $i<$arrCount; $i++) { list($redCouponIdList, $restRedAmount) = getBestCoupon($redCoupons, $restRedAmount); if ($restRedAmount == 0) { $bestCouponIdList = $redCouponIdList; break; } $redCouponIdLists[] = $redCouponIdList; $restRedAmounts[] = $restRedAmount; array_shift($redCoupons); } if (empty($bestCouponIdList)) { $pos = array_search(min($restRedAmounts), $restRedAmounts); $bestCouponIdList = $redCouponIdLists[$pos]; } } /** * 红包最优算法 */ private function getBestCoupon($redCoupons, $restRedAmount) { $redCouponAmount = 0; foreach ($redCoupons as $redCoupon) { if ($restRedAmount >= $redCoupon->getAmount()) { $redCouponAmount = $redCouponAmount + $redCoupon->getAmount()); $redCouponIdList[] = $redCoupon->getCouponId(); $restRedAmount = $restRedAmount - $redCoupon->getAmount(); if ($restRedAmount == 0) break; } } return [$redCouponIdList, $restRedAmount]; }
实例解析:用户投资9000,用户有优惠券(50,30,30,30,30)
用50块尝试,最多80
用第一个30尝试,最多90,已经最优,中断程序(否则继续向下类推)
问题
因为每次算完就把该红包从数组中推出,这样还是存在问题。例如投资1600,用户有(100,50,30,30)。这样就不会出现最优。
解决(算法2.0)
不把计算过优惠券推出,需要每次把要计算那张优惠券单独拿出来
这样程序复杂了很多,但还是可以实现的
这样还是会出现算法1.0的问题,不过这种按照顺序取优惠券很难不出现问题。但是这种面额的优惠券出现几率几乎没有
请教
期待有大神给出更好的算法
相关推荐
聚沙成塔积水成渊 2020-08-16
chvnetcom 2020-04-26
木子叶家园 2020-03-06
VanTYS 2019-12-26
xiaonao00 2019-12-11
JDWell 2019-11-01
tifosiboy 2019-10-25
81206230 2015-09-16
lizhiyong 2019-06-28
baohuanlove 2019-06-20
一线码农 2016-02-20
jasonchen 2015-09-15
前端外刊评论 2017-12-16
前端外刊评论 2017-12-16
科技蟹 2017-10-09
编程爱好者联盟 2017-05-06
网络游戏 2017-04-11
互联网小兵 2016-11-11