故事是这样的:某百货公司购买化妆品有促销活动,每支付 1 元返 0.22 元,但返的钱必须下次才能用来消费(且无法兑换现金),且只能 1 元 1 元地花(例如返了 1.1 元,则下次可以抵扣 0 或 1 元)。
熟知这种情况下最理想的支付金额是名义价格的 1/(1+22%),相当于八二折。但是必须精巧地购买才能达到这样的效果——给定一个购物列表,如何寻求一种“最优”的支付顺序——最优是希望支付的现金尽量少——呢?
如果限制只允许支付两次,则该问题是 NP-困难的。对于现实世界的遇到的情况,如果允许支付 3 次,则可以按照这种方式来购物:
具体如何找到第一单和第二单我还没仔细想——当然,在现实世界里,这个问题用贪心算法对付基本上都是 ok 的,实在不行上 naive 的动态规划,也不会很慢。
详细内容参见 Discount aux Galeries Lafayette and NP-completeness——这篇文章主体是英语,夹杂一些法语和汉语。
其实这是一篇骗博文访问量的哈哈哈哈~
1
elviscai 2017-12-23 21:02:31 +08:00
已 Block,谢谢
|
2
cominghome 2017-12-27 10:20:44 +08:00
老实说,这个 blog 排版有什么讲究吗?
是滚轮不好用吗 |
3
geelaw OP @cominghome 如果你的屏幕足够宽,你需要使用 Ctrl+Shift+滚轮 来左右滚动,不提供自动处理变向的原因是我懒。另一种用法是把窗口宽度降低,这样就会变成不分栏的排版,就可以用滚轮上下滚动页面。
|