优秀书籍某出版社的《哈里波特》系列共有5卷,每本单卖都是8块钱,如果读者一次购买不同的k(k>2)卷,就可以享受不同的折扣优惠,如下所示:求,如果买一批书的最低价格,即最大折扣符
优秀书籍
某出版社的《哈里波特》系列共有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种情况