《编程之美》读书笔记(四)：卖书折扣问题的贪心解法
每次看完《编程之美》中的问题，想要亲自演算一下或深入思考的时候，都觉得时间过得很快，动辄一两个小时，如果再把代码敲一遍的话，需要的时间可能更长，真是搞不懂通过微软面试的那些家伙的脑袋到底什么构造，书的序言中提到他们每次面试45分钟，还要写出程序？！在我看来，如果是控制CPU曲线或是中国象棋问题或许还有可能，如果是买书折扣问题，我觉得真的是不太容易，尤其是如果当面试者钻进本题的贪心解法而不是动态规划算法的思路之后，因为我写这篇文章前前后后大概用了5个小时 :-( 。不过我想只要是学习就不是浪费时间，今天上网看到微软的校园招聘网站又有更新，等我把这本书看完，就投简历过去试一试 :-) 。
1 问题描述及分析
买书折扣问题的描述是，某出版社的《哈里波特》系列共有5卷，每本单卖都是8块钱，如果读者一次购买不同的k（k>=2）卷，就可以享受不同的折扣优惠，如下所示：
问题是如果给定一个订单，如何计算出最大的折扣数？
书中给出的动态规划解法这里就不再赘述了。不过，里面有两个问题需要单独关注一下：(1)如果订单描述为（X1，X2，X3，X4，X5），其中X1-X5为所订数的数量，其所在位置为卷的编号，即第一卷X1本，第二卷X2本，…，第5卷X5本；如果订单为：（X3，X2，X4，X5，X1），则表示第一卷X3本，第二卷X2本，…，第五卷X1本。我们可以很容易的看到，由于每本书的价格相同，所以折扣的多少仅仅在于如何选取而不在于究竟取那一卷书。因此，上面两个订单的最大折扣数是相同的，这也使得我们可以使用统一的方法（Y1，Y2，Y3，Y4，Y5），其中Y1≥Y1≥Y1≥Y1≥Y5，来表示一个订单。作者将每本书的定价设为相同的是为了简化问题，因为如果每本书的定价也不同，则问题就会变得更加复杂，这时我们就不能仅仅考虑选几本书，还要考虑选哪几本。