求分享一个最接近的算法

[maxsec]

场景：

优惠券。
老板不想让用户自己选优惠券，优惠券可以叠加，优先于余额自动选择最优匹配方案来抵扣。

比方说：
用户买100块钱的东西，
用户有1张100元优惠券和1张50元优惠券，就使用100券来抵扣；

或者用户买100元的东西，
用户有1张101元优惠券和2张50元优惠券，自动使用2 x 50来抵扣；

用户买105的东西，
用户有3张50元优惠券和2张20优惠券，自动使用2 x 50 + 20来抵扣


求大神～

[canesten]

不能理解第三种
到底是保证优惠劵最大化消耗
还是保证优惠券最大化利用？

[dingyaguang117]

同不能理解第三种

[iptux]

背包算法变种？

[llbbzh]

第二和第三种矛盾啊

[lecher]

楼主的本意应该是，优惠券可以覆盖消费的情况下，尽可能少的消耗吧。
背包算法呀。而且只背一个包，排序好的数组内元素加和最接近目标数的情况下，选可以覆盖目标数的组合。

[pimin]

1.既然优惠券可以叠加，那使用上肯定以大额优先，小额客户下次使用更方便
比如我有10×10，20×5，50×3，100×2
买100块的东西，你给我用了10×10，下次我买10块的东西怎么办
2.我觉得可以叠加的优惠券可以考虑直接做成充值券//这个只是乱说的
3.105块付款是付100+10还是付100+5块额外付款，我觉得这个要给客户选择

大额优先的话算法就很简单了吧。

[GTim]

小额优先,好会算计的老板,这样意味着最后一次一定要忍痛割爱使用大额的点券.
我给出大额优先+替换法.
1. 计算大额优先法得出的结果.
2. 然后开始循环已经生成的结果:用次大额去替换最大额.比如3张20元可以替换一张50元.ps:为什么不是1张10元+20张20元去替换呢:因为这样更容易理解,何况20元的终究要替换成10元,什么时候替换都一样不是)

[GTim]

@GTim 为什么很会算计呢?因为点券都是有过期时间的,每次都最小额,那么大额的肯定会剩下到过期或者到最后不得不买一个本来只使用10元的点券变成了使用100元的点券.这就是为公司缩减陈本

[akfish]

不就是线性规划问题么。
目标函数f为使用的礼券总和，就是用户礼券额度的线性组合。
f = A*T
A是系数矩阵，T是礼券额度矩阵。
在满足f <= p的约束条件下，求解使f最大化A，就是你要的结果。

[akfish]

补充下：
p是用户购买商品的总价。
在这个问题里面A和T都退化为向量。

A向量的元素取值在0~1之间。
T向量的每个元素是用户所有的某种礼券的总额。
例，有4种礼券50/100/200/500用户分别有3张，0张，2张，1张，用户购买了p = 1234元的商品，此时：
T = [150 0 400 500]
A = [a1 a2 a3 a4]

在f <= 1234时，求解A使f = A * T最大化。
问题就是这样建模的，懂点线性代数的，到这里就很简单了。

http://en.wikipedia.org/wiki/Linear_programming

[maxsec]

@dingyaguang117
不矛盾，意思就是如果有一种方案会浪费哪怕1元面值，也要选择另外一种不浪费1分钱面值的方案。

[66CCFF]

背包算法，取到消费额度绝对值最小的那组

[gihnius]

101元优惠券 这个太坑了吧！？

[Magic347]

这个问题直觉上贪心法可解，不知楼主最终采用什么方案了？