薅个羊毛都这么麻烦么

[geelaw]

故事是这样的：某百货公司购买化妆品有促销活动，每支付 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——这篇文章主体是英语，夹杂一些法语和汉语。

---

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

[elviscai]

已 Block，谢谢

[cominghome]

老实说，这个 blog 排版有什么讲究吗？
是滚轮不好用吗

[geelaw]

@cominghome 如果你的屏幕足够宽，你需要使用 Ctrl+Shift+滚轮 来左右滚动，不提供自动处理变向的原因是我懒。另一种用法是把窗口宽度降低，这样就会变成不分栏的排版，就可以用滚轮上下滚动页面。