V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
maxsec
V2EX  ›  程序员

求分享一个最接近的算法

  •  
  •   maxsec · 2014-08-23 14:05:42 +08:00 · 3662 次点击
    这是一个创建于 3734 天前的主题,其中的信息可能已经有所发展或是发生改变。
    场景:

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

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

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

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


    求大神~
    14 条回复    2014-12-22 17:56:58 +08:00
    canesten
        1
    canesten  
       2014-08-23 14:11:26 +08:00
    不能理解第三种
    到底是保证优惠劵最大化消耗
    还是保证优惠券最大化利用?
    dingyaguang117
        2
    dingyaguang117  
       2014-08-23 14:15:29 +08:00
    同不能理解第三种
    iptux
        3
    iptux  
       2014-08-23 14:18:14 +08:00
    背包算法变种?
    llbbzh
        4
    llbbzh  
       2014-08-23 14:21:07 +08:00
    第二和第三种矛盾啊
    lecher
        5
    lecher  
       2014-08-23 14:45:28 +08:00
    楼主的本意应该是,优惠券可以覆盖消费的情况下,尽可能少的消耗吧。
    背包算法呀。而且只背一个包,排序好的数组内元素加和最接近目标数的情况下,选可以覆盖目标数的组合。
    pimin
        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块额外付款,我觉得这个要给客户选择

    大额优先的话算法就很简单了吧。
    GTim
        7
    GTim  
       2014-08-23 16:21:57 +08:00
    小额优先,好会算计的老板,这样意味着最后一次一定要忍痛割爱使用大额的点券.
    我给出大额优先+替换法.
    1. 计算大额优先法得出的结果.
    2. 然后开始循环已经生成的结果:用次大额去替换最大额.比如3张20元可以替换一张50元.ps:为什么不是1张10元+20张20元去替换呢:因为这样更容易理解,何况20元的终究要替换成10元,什么时候替换都一样不是)
    GTim
        8
    GTim  
       2014-08-23 16:24:47 +08:00
    @GTim 为什么很会算计呢?因为点券都是有过期时间的,每次都最小额,那么大额的肯定会剩下到过期或者到最后不得不买一个本来只使用10元的点券变成了使用100元的点券.这就是为公司缩减陈本
    akfish
        9
    akfish  
       2014-08-23 16:57:35 +08:00
    不就是线性规划问题么。
    目标函数f为使用的礼券总和,就是用户礼券额度的线性组合。
    f = A*T
    A是系数矩阵,T是礼券额度矩阵。
    在满足f <= p的约束条件下,求解使f最大化A,就是你要的结果。
    akfish
        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
    maxsec
        11
    maxsec  
    OP
       2014-08-23 18:18:07 +08:00
    @dingyaguang117
    不矛盾,意思就是如果有一种方案会浪费哪怕1元面值,也要选择另外一种不浪费1分钱面值的方案。
    66CCFF
        12
    66CCFF  
       2014-08-23 19:22:09 +08:00
    背包算法,取到消费额度绝对值最小的那组
    gihnius
        13
    gihnius  
       2014-08-23 20:23:19 +08:00
    101元优惠券 这个太坑了吧!?
    Magic347
        14
    Magic347  
       2014-12-22 17:56:58 +08:00
    这个问题直觉上贪心法可解,不知楼主最终采用什么方案了?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1048 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 20:14 · PVG 04:14 · LAX 12:14 · JFK 15:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.