从买书那天算起，到今天已经过了半个多月。这段时间说短不短，如果是一本300多页的小说的话，我大概一天就能搞定（我的记录是一天一千多页《大唐双龙传》），但是到现在《编程之美》我只看了不到50页。虽然我不是天天看，但是一旦我看了一个问题之后，我就希望能够把这个问题在算法层面分析透，这份专注是我以前看《算法导论》或者上算法课的时候所不曾体会到的。究其原因，主要还是纯粹的理论流于枯燥，纯粹的应用不免肤浅，而这本书的定位刚刚好，既能够以应用带动算法的学习，又能够避免过于说教的风格。

尽管初衷不错，但我仍觉拿捏得尺度有待商榷。因为编程应该既严谨又灵活，严谨的思考保证了程序运行的稳定，而灵活的思维则为创新提供了条件。而“编程之美”给我的感觉是灵活有余严谨不足。我觉得既然是有关算法的书，那么在一些关键点上的证明就不可或缺，例如在我看的六个问题中就出现两个贪心算法没证明其贪心选择性，或讨论的不够，其中“买书问题”的贪心选择还是有问题的。当然，我们不应该奢求这本定位于“面试题集”的书能够写出如“算法导论”般严格的证明。但至少应该给出具体思路，以证明想法是有依据而非直观感觉（因为我们的直观感觉在很多时候是不准确的，就比如我的读书笔记四种分析买书问题，如果把三本书的折扣改成15%，那我们就有可能被得到的折扣表格所误导而采用原始的贪心算法）；最可怕的是鉴于构建反例实际是一件非常困难的事情，所以我们从给出的例子中可能也无法看出端倪。此外，在看书过程中所遇到的各种错误的数量也是屡创新高。听说马上就要出第二版了，真是为后面的内容担心，难道最后又要附一页勘误表？

虽然问题多多，但由于瑕不掩瑜，我们仍然能够从书中获得足够多的微软人的智慧，哪怕是促使我们重新温习一遍算法基础也好，希望第四版（ 如果有的话:-) ）能看到一个完美的“编程之美”。

    1 问题描述及分析

本题所说的问题是微软每天为员工提供各种不同的饮料，如可乐，酸奶，豆浆，咖啡，绿茶……..（待遇不错啊，呵呵），饮料i的单位容量为V_i，其中每种饮料单个容量都是2的方幂，员工对饮料i的满意度为H_i，冰柜的总容量为V（每天必须装满），问题是如何组合现有的各种饮料，使总的满意度最高。

还是说一下我的第一印象，很显然这是一道最优化问题，但很容易想到这道题和线性规划的描述很符合，但是由于解线性规划的单纯型方法比较复杂，这里就不再讨论了。其次，回想一下经典的0-1背包问题，和本问题也有些相似，所不同的是0-1背包问题中，每件物品只能拿一次，而这里同一种饮料能拿多瓶；此外，原问题中每天供应的总量V是必须达到的（否则会有员工投诉？），所以不能够像0-1背包问题那样有让背包装不满的情况。这个条件实际上改变了我们对于最优解的搜索策略，因为容量为V的装饮料的冰柜每天早晨都必须是满的，所以即便有另一个使满意度最高但冰柜不满的组合我们也是不能选的。

其实我们可以稍微改变一下本题的条件，忽略原问题中的每种饮料单个容量都是2的方幂的条件，并允许冰柜不满的情况下求最大满意度的组合，希望可以使原问题的解决更富有一般性。