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

薅个羊毛都这么麻烦么

  •  
  •   geelaw · 2017-12-23 02:10:45 +08:00 · 2609 次点击
    这是一个创建于 2509 天前的主题,其中的信息可能已经有所发展或是发生改变。

    故事是这样的:某百货公司购买化妆品有促销活动,每支付 1 元返 0.22 元,但返的钱必须下次才能用来消费(且无法兑换现金),且只能 1 元 1 元地花(例如返了 1.1 元,则下次可以抵扣 0 或 1 元)。

    熟知这种情况下最理想的支付金额是名义价格的 1/(1+22%),相当于八二折。但是必须精巧地购买才能达到这样的效果——给定一个购物列表,如何寻求一种“最优”的支付顺序——最优是希望支付的现金尽量少——呢?

    如果限制只允许支付两次,则该问题是 NP-困难的。对于现实世界的遇到的情况,如果允许支付 3 次,则可以按照这种方式来购物:

    1. 下一单比较大的,金额接近 总价 /1.22 ,但不要超过;这一轮获得很多积分;
    2. 下一单比较小的,使得完成这单之后的总名义价格稍微超过 总价 /1.22 ;这一轮要仔细计算花费的积分,使得这一单完成后,总支出等于 总价 /1.22 ;
    3. 最后一单,几乎全都是用积分支付的,可能有一两块钱的尾款。

    具体如何找到第一单和第二单我还没仔细想——当然,在现实世界里,这个问题用贪心算法对付基本上都是 ok 的,实在不行上 naive 的动态规划,也不会很慢。

    详细内容参见 Discount aux Galeries Lafayette and NP-completeness——这篇文章主体是英语,夹杂一些法语和汉语。


    其实这是一篇骗博文访问量的哈哈哈哈~

    3 条回复    2017-12-27 10:55:37 +08:00
    elviscai
        1
    elviscai  
       2017-12-23 21:02:31 +08:00
    已 Block,谢谢
    cominghome
        2
    cominghome  
       2017-12-27 10:20:44 +08:00
    老实说,这个 blog 排版有什么讲究吗?
    是滚轮不好用吗
    geelaw
        3
    geelaw  
    OP
       2017-12-27 10:55:37 +08:00 via iPhone
    @cominghome 如果你的屏幕足够宽,你需要使用 Ctrl+Shift+滚轮 来左右滚动,不提供自动处理变向的原因是我懒。另一种用法是把窗口宽度降低,这样就会变成不分栏的排版,就可以用滚轮上下滚动页面。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3588 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 04:34 · PVG 12:34 · LAX 20:34 · JFK 23:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.