1. 背景

我有一个朋友，最近在做商场代购。看上去有些类似社区团购。比如商场搞活动，满500返150的购物券。如果一个用户买了件500多块钱的商品，返了150的券可能也买不了其他什么东西。而如果有四个用户的话，返的券就可以再买一件商品。我朋友于是就通过自己的渠道收集订单，拼成大单去商场采购，以期最大限度地利用优惠。这样用户更容易得到优惠，商家能卖更多货，我朋友也能赚点差价，一举多得。

不过我朋友发现订单一多，手动拼单就很麻烦，而且拼出来的订单比最优的折扣总是差挺多，甚至有时候还不如商场柜台里的柜姐拼出来的好。于是就来问我，看看我有什么办法。

2. 问题分析

我眉头一皱，发现这是个组合最优化问题，才疏学浅一时没想到有什么现成的方案。于是我问我朋友是怎么解决这个问题的。我朋友说，柜台通常是把订单分成两部分，让第一部分订单的返券额度恰好覆盖第二部分的订单金额就可以了。我一听这不就是0/1背包问题吗？一堆物品只需选择放进背包和不放进背包就可以了。没想到本人计算机专业毕业10多年了，终于在现实中遇到了能用动态规划解决的问题了！

3. 实现

看动态规划的方法之前，先来看看我朋友的方法。我朋友用的是贪心的方法。我们知道贪心只能给出近似解，不一定是最优解，所以我朋友去商场采购时才会因为凑得不够好而被柜姐鄙视。

3.1 贪心

因为我朋友希望能尽快凑满第一部分订单，所以先把商品按照价格降序排序，然后遍历商品列表，直到列表前半商品的返券恰好能覆盖后半商品的金额。例如，有如下商品

商品1    450元
商品2    330元
商品3    980元
商品4    260元

按价格降序排序后

商品3    980元
商品1    450元
商品2    330元
商品4    260元

拆分后

订单1
-------------
商品3    980元
商品1    450元
商品2    330元
-------------
金额    1760元
返券     450元

订单2
-------------
商品4    260元
-------------
金额     260元
剩余返券  190元

=============
原价    2020元
实付    1760元
折扣    87.13%

可以看到不仅返券没用完，最终折扣也离最优折扣 500 / (500 + 150) = 76.92% 相差甚远。

3.2 动态规划

将这个问题转化一下就可以用 0/1 背包求解。0/1 背包的限制是背包内商品总重量weights(selectedItems) <= capacity，最优化目标是背包内商品总价值max(price(selectedItems))。而这个问题的限制是:

# paidItems: 需支付的商品
# allItems: 全部商品
# price(items): 商品金额
# bonus(price): 金额返券
bonus(price(paidItems)) >= price(allItems - paidItems)

最优化目标是:

min(price(paidItems))

还是上面的例子，求解后

订单1
-------------
商品2    330元
商品4    260元
商品3    980元
-------------
金额    1570元
返券     450元

订单2
-------------
商品1    450元
-------------
金额     450元
剩余返券    0元

=============
原价    2020元
实付    1570元
折扣    77.72%

可以看到折扣一下子就低了近10个百分点，返券也没有浪费。

3.3 优化

前面的方法给出的解，都是第一笔订单的返现额度大于第二笔订单的金额。而在实际购买时，如果返券金额不够，是可以继续支付补足差额的。那么补差额会不会更优呢？答案是会的。比如这样的情况：

订单1
-------------
商品1   1540元x4
商品2    315元
-------------
金额    6475元
返券    1800元

订单2
-------------
商品1   1540元
商品3    240元
-------------
金额    1780元
剩余返券   20元

=============
原价    8255元
实付    6475元
折扣    78.44%

如果允许补差额的话，可以这样凑：

订单1
-------------
商品1   1540元x4
-------------
金额    6160元
返券    1800元

订单2
-------------
商品1   1540元
商品2    315元
商品3    240元
-------------
金额    2095元
剩余返券 -295元

=============
原价    8255元
实付    6455元
折扣    78.20%

所以在寻找最优解的时候，同样需要考虑补差额的情况。

4. 额外限制条件

我把我算出来的结果给我朋友看，不料我朋友并没有很兴奋。我朋友说，这只是最基本的情况。实际采购时会有各种限制。比如商场搞活动时，会实行一定的限购。比如要求每笔订单的金额不超过8000元，和/或每笔订单中单件商品的数量不超过8件。这样的话采购的商品一多，就没法只拆成两单采购，而必须拆成多单才行。

于是问题就变成了把商品分成两组，每组多单，拿第一组里每单的返券去购买第二组里的每单。这样把商品归入多个订单中的哪个订单的问题就成了多背包问题，应该是NP完全问题，只能指望近似解了。

4.1 贪心

首先想到的是在满足限制条件的情况下尽可能多凑出不浪费返券的订单对。比如订单限额8000，返券就是8000 / 500 * 150 = 2400，那么就需要尽可能多地凑出8000元和2400元的订单，这样至少能保证这些订单中的商品享受的折扣是最优的。而每次凑单就是一个限定了目标金额的 0/1 背包问题。

从我朋友那边拿了一批总价10w的商品跑了下，最优的情况应该能凑出9单(100000 / (8000 + 2400))，但实际只凑出了8单，最终的折扣是77.48%。

4.2 随机初始化

由于整个求解的过程是确定的，所以在不修改算法的情况下无法进一步优化结果。这里尝试借鉴模拟退火的思想，为算法加入随机性。具体来说，每次执行前会先把商品列表打乱。这样做了以后，几次就凑出了理想情况下的9单，最终折扣是77.31%。

4.3 最终阶段优化

在上面的算法中，在凑完了最优的订单之后，对最后总价小于(8000 + 2400)的商品，又凑出了像3000返900、2000返600、1000返300这样多个订单。因为这些订单不是最优折扣，所以这样的订单数量越多，最终折扣就越差。其实这里可以复用最上面的 0/1 背包的方法，只凑一单出来以减少损失。这样做的结果使得最终折扣为76.96%，离最优的76.92%仅一步之遥。

5. 小结

从结果上看，由于我朋友的生意不大，0.5个百分点的优化能带来的收益非常有限。10w的订单也就500块钱的差距，请吃顿饭就差不多了。希望我朋友能早日把摊子做大，月流水能有一个小目标的话优化带来的差距就有50w了，一年下来能省一套房。毕竟工程师只是能用50块钱搞定任何人用100块钱都能搞定的问题，工程师的价值只有在基数足够大时才能体现出来。