每次看完《编程之美》中的问题，想要亲自演算一下或深入思考的时候，都觉得时间过得很快，动辄一两个小时，如果再把代码敲一遍的话，需要的时间可能更长，真是搞不懂通过微软面试的那些家伙的脑袋到底什么构造，书的序言中提到他们每次面试45分钟，还要写出程序？！在我看来，如果是控制CPU曲线或是中国象棋问题或许还有可能，如果是买书折扣问题，我觉得真的是不太容易，尤其是如果当面试者钻进本题的贪心解法而不是动态规划算法的思路之后，因为我写这篇文章前前后后大概用了5个小时 :-( 。不过我想只要是学习就不是浪费时间，今天上网看到微软的校园招聘网站又有更新，等我把这本书看完，就投简历过去试一试 :-) 。
1 问题描述及分析
买书折扣问题的描述是，某出版社的《哈里波特》系列共有5卷，每本单卖都是8块钱，如果读者一次购买不同的k（k>=2）卷，就可以享受不同的折扣优惠，如下所示：
问题是如果给定一个订单，如何计算出最大的折扣数？
Read full article from 《编程之美》读书笔记(四): 卖书折扣问题的贪心解法 - 薛笛的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment