1
canesten 2014-08-23 14:11:26 +08:00
不能理解第三种
到底是保证优惠劵最大化消耗 还是保证优惠券最大化利用? |
2
dingyaguang117 2014-08-23 14:15:29 +08:00
同不能理解第三种
|
3
iptux 2014-08-23 14:18:14 +08:00
背包算法变种?
|
4
llbbzh 2014-08-23 14:21:07 +08:00
第二和第三种矛盾啊
|
5
lecher 2014-08-23 14:45:28 +08:00
楼主的本意应该是,优惠券可以覆盖消费的情况下,尽可能少的消耗吧。
背包算法呀。而且只背一个包,排序好的数组内元素加和最接近目标数的情况下,选可以覆盖目标数的组合。 |
6
pimin 2014-08-23 14:46:55 +08:00
1.既然优惠券可以叠加,那使用上肯定以大额优先,小额客户下次使用更方便
比如我有10×10,20×5,50×3,100×2 买100块的东西,你给我用了10×10,下次我买10块的东西怎么办 2.我觉得可以叠加的优惠券可以考虑直接做成充值券//这个只是乱说的 3.105块付款是付100+10还是付100+5块额外付款,我觉得这个要给客户选择 大额优先的话算法就很简单了吧。 |
7
GTim 2014-08-23 16:21:57 +08:00
小额优先,好会算计的老板,这样意味着最后一次一定要忍痛割爱使用大额的点券.
我给出大额优先+替换法. 1. 计算大额优先法得出的结果. 2. 然后开始循环已经生成的结果:用次大额去替换最大额.比如3张20元可以替换一张50元.ps:为什么不是1张10元+20张20元去替换呢:因为这样更容易理解,何况20元的终究要替换成10元,什么时候替换都一样不是) |
8
GTim 2014-08-23 16:24:47 +08:00
@GTim 为什么很会算计呢?因为点券都是有过期时间的,每次都最小额,那么大额的肯定会剩下到过期或者到最后不得不买一个本来只使用10元的点券变成了使用100元的点券.这就是为公司缩减陈本
|
9
akfish 2014-08-23 16:57:35 +08:00
不就是线性规划问题么。
目标函数f为使用的礼券总和,就是用户礼券额度的线性组合。 f = A*T A是系数矩阵,T是礼券额度矩阵。 在满足f <= p的约束条件下,求解使f最大化A,就是你要的结果。 |
10
akfish 2014-08-23 17:06:56 +08:00
补充下:
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 |
11
maxsec OP @dingyaguang117
不矛盾,意思就是如果有一种方案会浪费哪怕1元面值,也要选择另外一种不浪费1分钱面值的方案。 |
12
66CCFF 2014-08-23 19:22:09 +08:00
背包算法,取到消费额度绝对值最小的那组
|
13
gihnius 2014-08-23 20:23:19 +08:00
101元优惠券 这个太坑了吧!?
|
14
Magic347 2014-12-22 17:56:58 +08:00
这个问题直觉上贪心法可解,不知楼主最终采用什么方案了?
|