故事是这样的:某百货公司购买化妆品有促销活动,每支付 1 元返 0.22 元,但返的钱必须下次才能用来消费(且无法兑换现金),且只能 1 元 1 元地花(例如返了 1.1 元,则下次可以抵扣 0 或 1 元)。
熟知这种情况下最理想的支付金额是名义价格的 1/(1+22%),相当于八二折。但是必须精巧地购买才能达到这样的效果——给定一个购物列表,如何寻求一种“最优”的支付顺序——最优是希望支付的现金尽量少——呢?
如果限制只允许支付两次,则该问题是 NP-困难的。对于现实世界的遇到的情况,如果允许支付 3 次,则可以按照这种方式来购物:
具体如何找到第一单和第二单我还没仔细想——当然,在现实世界里,这个问题用贪心算法对付基本上都是 ok 的,实在不行上 naive 的动态规划,也不会很慢。
详细内容参见 Discount aux Galeries Lafayette and NP-completeness——这篇文章主体是英语,夹杂一些法语和汉语。
其实这是一篇骗博文访问量的哈哈哈哈~
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.