《编程之美》1.4买书问题的常数时间解法

优秀书籍

某出版社的《哈里波特》系列共有5卷，每本单卖都是8块钱，如果读者一次购买不同的k（k>=2）卷，就可以享受不同的折扣优惠，如下所示：

求，如果买一批书的最低价格，即最大折扣

符号说明：

按照书上的记法，假设Y1>=Y2>=Y3>=Y4>=Y5>=0，n=Y1+Y2+Y3+Y4+Y5

假设a,b,c,d,e分别是5本书的名字，仅仅是名字，不是变量

用【ab】表示1个部分有2本书，是a和b，这2本书享受2本书的5%的折扣，用【acde】表示1个部分有4本书等等以此类推

在《编程之美》1.4买书问题的简化版本一文中，提到了11个条件和11个结论，

虽然这11个结论对本题已经不成立了，但是这11个条件却还成立，但是叙述上得改一下。

以（4,4,4）<（5,5,2）为例，原本的叙述是，如果可以拆分成4+4+4，那么自然也可以拆分成5+5+2，这样折扣就变大了。但是这里的叙述是，如果可以拆分成4+4+4，而且也可以拆分成5+5+2，那么5+5+2的折扣就大一些。

也就是说，因为有着书分为不同的5卷这个限制，可以拆分成4+4+4的12本书不一定可以拆分成5+5+2。

定理一，所有的大小为1的部分可以表示成若干个（若干个可能是0个，下同）【a】

证明：因为（1,1）<（2）所以【a】和【b】不共存，否则可以用【ab】代替

定理二，所有的大小为2的部分可以表示成若干个【ab】和若干个【ac】

证明：因为（2,2）<（4）所以【ab】和【cd】不能共存

因为（2,2,2）<（3,3）所以【ab】【bc】【ac】不能共存，否则可以用【abc】和【abc】这2个部分代替

因为（2,2,2）（1,1,4）所以【ab】【ac】【ad】不能共存，否则可以用【a】【a】【abcd】这3个部分代替

综合这3个限制即可得到定理二

定理三，所有的大小为3的部分可以表示成若干个【abc】

证明：因为（3,3）<（2,4），所以【abc】和【abd】不能共存，否则可以用【abcd】和【ab】这2个部分代替

而且【abc】和【ade】不能共存，否则可以用【abcd】和【ae】这2个部分代替

所以2个不一样的大小为3的部分是不能共存的

定理四，所有的大小为4的部分可以表示成若干个【abcd】和若干个【abce】

证明：因为（4,4,4）<（2,5,5）所以【abcd】【abce】【abde】不能共存，否则可以用【abcde】和【abcde】和【ab】这3个部分代替

所以3个不一样的大小为4的部分是不能共存的

定理五，n本书可以表示成若干个【a】和若干个【ab】和若干个【ac】和若干个【abc】和若干个【abcd】和若干个【abce】和若干个【abcde】

证明：首先根据定理四可得，大小为4或5的部分可以表示成若干个【abcd】和若干个【abce】和若干个【abcde】

注意：定理三只是说2个不一样的大小为3的部分是不能共存的，在没有限制条件下可以不妨设都是【abc】，但是在现在已经表示出大小为4或5的部分之后，就不能这样不妨设了，还需要别的条件才行。

因为（3,4）<（2,5），所以如果2个部分分别有3本书和4本书，那么这4本书一定包含这3本书，例如【abc】和【abcd】

注意，这里不能根据【abcd】和【abce】求交集得到大小为3的部分只能是【abc】，因为【abcd】和【abce】都可能不存在，还可能都不存在。但是，无论【abcd】是否存在，也无论【abce】是否存在，都可以不妨设大小为3的部分都是【abc】

因为（2,3）<（1,4），所以如果2个部分分别有2本书和3本书，那么这3本书一定包含这2本书，例如【ab】和【abd】

因为（2,4）<（1,5），所以如果2个部分分别有2本书和4本书，那么这4本书一定包含这2本书，例如【ab】和【abde】

同上，根据定理二，无论【abcd】是否存在，也无论【abce】是否存在，也无论【abc】是否存在，都可以不妨设所有的大小为2的部分可以表示成若干个【ab】和若干个【ac】

同理，因为（1,2）<（3），（1,3）<（4），（1,4）<（5），所以根据定理一，无论【abcd】是否存在，也无论【abce】是否存在，也无论【abc】是否存在，也无论【ab】是否存在，也无论【ac】是否存在，都可以不妨设所有的大小为1的部分可以表示成若干个【a】

综上可得定理五

下面根据定理五求解n可能表示成哪几种情况

因为（1,3）<（2,2），所以2个部分分别有1本书和3本书是不可能的，即n1*n3=0

因为（3,5）<（4,4），所以2个部分分别有3本书和5本书是不可能的，即n3*n5=0

因为（2,2,5）<（1,4,4），所以【ab】和【ac】和【abcde】不能共存，否则可以用【a】【abcd】【abce】这3个部分代替

第1种情况，n3!=0

那么n1=0，n5=0，n本书是若干个【ab】和若干个【ac】和至少1个【abc】和若干个【abcd】和若干个【abce】

第2种情况，n3=0且n5!=0

那么【ab】和【ac】不能共存，不妨设【ac】不存在

那么n本书是若干个【a】和若干个【ab】和若干个【abcd】和若干个【abce】和至少1个【abcde】

第3种情况，n3=0且n5=0

那么n本书是若干个【a】和若干个【ab】和若干个【ac】和若干个【abcd】和若干个【abce】

下面讨论根据Y1>=Y2>=Y3>=Y4>=Y5>=0，如何求出n的准确表示

首先，如何区分这3种情况？

第1种情况中，c的数量大于d和e的数量之和，a和d和e的数量之和小于b和c的数量之和

第2种情况中，c的数量小于d和e的数量之和

第3种情况中，c的数量大于或等于d和e的数量之和，a和d和e的数量之和大于或等于b和c的数量之和

这样就区分开了3种情况。

现在的问题是abcde和Y1Y2Y3Y4Y5如何对应？

神奇的是，不妨设a对应Y1，b对应Y2，c对应Y3，d对应Y4，e对应Y5

于是得到下列结论：

第1种情况是Y1-Y3个【ab】和Y1-Y2个【ac】和Y2+Y3-Y1-Y4-Y5>0个【abc】和Y4个【abcd】和Y5个【abce】

第2种情况是Y1-Y2个【a】和Y2-Y3个【ab】和Y3-Y5个【abcd】和Y3-Y4个【abce】和Y4+Y5-Y3>0个【abcde】

第3种情况是Y1+Y4+Y5-Y2-Y3个【a】和Y2-Y4-Y5个【ab】和Y3-Y4-Y5个【ac】和Y4个【abcd】和Y5个【abce】

如果Y4+Y5-Y3>0就是第2种情况，否则的话

如果Y2+Y3-Y1-Y4-Y5>0就是第1种情况，否则就是第3种情况

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/53333514