《编程之美》读书笔记03: 1.4 买书问题
问题:
在节假日的时候,书店一般都会做促销活动。由于《哈利波特》系列相当畅销,店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中,一共有五卷,用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷,就可以扣除5%的费用,三卷则更多。假设具体折扣的情况如下:
本数
|
折扣
|
2
|
5%
|
3
|
10%
|
4
|
20%
|
5
|
25%
|
在一份订单中,根据购买的卷数以及本书,就会出现可以应用不同折扣规则的情况。但是,一本书只会应用一个折扣规则。比如,读者一共买了两本卷一,一本卷二。那么,可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣,希望能够计算出的总额尽可能的低。
要求根据这样的需求,设计出算法,能够计算出读者所购买一批书的最低价格。
书中给出的解法:
如果要买的书为(Y1, Y2, Y3, Y4, Y5)(其中Y1>=Y2>=Y3>=Y4>=Y5),贪心策略建议我们买Y5本五卷的,Y4-Y5本四卷,Y3-Y4本三卷,Y2-Y3本两卷和Y1-Y2本一卷。由于贪心策略的反例,我们把K本五卷和K本三卷重新组合成2×K本四卷(K = min{Y5, Y3-Y4})。结果就是我们买Y5-K本五卷的,Y4-Y5本四卷,Y3-Y4-K本三卷,Y2-Y3本两卷和Y1-Y2本一卷(K = min{Y5, Y3-Y4})。比如我们要买3本第一卷,2本第二卷,6本第三卷,1本第四卷和7本第五卷,像前面所说的,我们要买的书可以用(7, 6, 3, 2, 1)表示。新的经过调整的贪心策略告诉我们应该买三本四卷,三本两卷和一本一卷。
㈠ 简单说明
假设共有m种书进行打折,总共要买n本。先将原来的折扣,转换成相对折扣(=最大折扣-原折扣)。若用F(n)表示买n本书时能得到最小相对折扣值(显然F(m)=0),则原折扣和(=n*最大折扣-F(n))必然最大。
若不考虑书的具体种类(即买书时对书的具体种类没要求),若采用贪心算法——每次尽可能的买m本,就要证明F(n)=F(n-m),或者找出F(n)=F(n-m)成立的条件。从后面的分析可知,当n大于某个数时,恒有F(n)=F(n-m)。
若考虑书的具体种类,比如5本时的状态(a1, a2, a3, a4, a5)(递减排列)。可以证明,最优解的买书次数必然是a1次。其它的买书解法,都可以从解法(a5次5卷,a4-a5次4卷,…,a1-a2次1卷),通过几个 i+j => (i-1)+(j+1) (5 >= i > j+1, j>=1) 调整得到(觉得这个从图中看很直观,但不好证明)。通过判断i+j => (i-1)+(j+1)对相对折扣值的影响,就可以判断书上的解法是否一定成立。
㈡ 不考虑书的具体种类
先考虑简单情况:对所买的书的具体种类没有要求。假设有m种书,共要买n本书,每次买的书的种类越多,每本书的折扣也越大。即m种时,折扣最大,用这个最大值减去每个折扣可得到相对折扣。要使总折扣最大,只要总相对折扣最小。用F(n)表示总相对折扣的最小值(显然:F(1)>F(2)>… >F(m-1)>F(m)=0,若定义F(0)=0,则F(m)=F(0))。显然F(k*m)=0,由于F(m-1)是第二小的, F(k*m-1)=F(m-1) (k为自然数)。
可以采用的贪心算法:每次尽可能的买m本书。若该贪心算法能找到最优解,则有:F(i)=F(i-m) (i>=m)。
性质1:若对任意自然数i∈[ k, m+k-1] (自然数k>=m), F(i)=F(i-m)均成立,
则对任意 i >= k,F(i)=F(i-m) 恒成立。
(证:由已知,当i∈ [ k, m+k-1] 时,命题F(i)=F(i-m)成立。
假设i=n (n>=m+k-1)时命题成立,则对任意i∈ [ k, n],F(i)=F(i-m)。
当i=n+1时,根据F(n)的定义及一次可买的书的卷数j(1 <= j <= m)可得:
F(n+1)= min{ F(j)+F(n+1-j)} (1 <= j <= m, k<= n+1-m <= n+1-j <= n)
=min{ F(j) + F(n+1-m-j)}
=F(n+1-m)
故i=n+1时命题仍成立。
因而,对任意 i >= k,F(i)=F(i-m)均成立。)
若要判断贪心算法(“每次尽可能买m本”)是否得到全局最优解,只要判断本数为m到2*m-1时是否都符合贪心算法,而m本和2*m-1本都是一定符合的,实际上只要判断本数为m+1到2*m-2时是否都得到全局最优解。
若设某次买的卷数为i(1<=i<=m),则剩余n-i,根据F(n-i)是否等于F(n-i-m),可将关于i的集合,分成两部分j、k,其中 F(n-j)=F(n-m-j),而F(n-k)!=F(n-m-k),显然:
F(n-m)=min{F(i)+F(n-m-i)} <= min{F(j)+F(n-m-j)}
F(n)= min{ F(j)+F(n-j),F(k)+F(n-k)}
= min{ F(j) + F(n-m-j), F(k) + F(n-k)}
>= min{ F(n-m), F(k) + F(n-k)}
上式若能取等号,则必满足下列条件之一:
① min{F(k)+F(n-k)} <= F(n-m)
② 集合j中存在某个值t(F(n-t)=F(n-m-t),1<=t<=m),满足F(n-m)=F(t)+F(n-m-t)。
若F(n-m)=F(n-2*m),即t=m,F(n)= min{ F(n-m), F(k) + F(n-k)}
对书上的折扣方案:
|
1
|
2
|
3
|
4
|
5
|
相对折扣
|
25%
|
20%
|
15%
|
5%
|
0
|
总相对折扣
|
25%
|
40%
|
45%
|
20%
|
0
|
F(6)=F(5)+F(1)=F(1) (按书上P32的分析得到“拆分成4+2折扣最大”的结论是错的。)
F(7)=F(5)+F(2)=F(2)
F(8)=F(4)+F(4) < F(3) + F(5)
F(9)=F(4)
F(10)=F(5)
F(11)=min( F(6), F(3)+F(8) )=F(6)
F(12)=min( F(7), F(4)+F(8) )=F(7)
F(13)=min( F(8), F(5)+F(8) )=F(8) (因为F(8)=F(5)+F(8),故可取等号)
购买本数为9到13时,都满足F(i)=F(i-5) (9<=i<=13),故i>=9时,均有 F(i)=F(i-5)。由于只有本数为8这一个例外,因而若采用贪心算法,能判断出是否将F(8)按F(3)计算,从而对结果进行调整,保证结果正确。
性质2: 存在整数k>=m,对任意整数 n >k, F(n)=F(n-m)恒成立。
证:
设买n-m本的最优解中,共有ai次每次买了i本书,则ai必定小于m,否则,ai次买i本,可以优化为i次买m本和ai-m次买i本。另外,必有ai <= i,否则,设j=ai > i,则j次每次买i本书,可以优化为i次每次买j本书。由于ai存在上界,可以假设t为i*ai(1<=i<=m-1)所有可能的乘积和中最大的,即t=max{sum(i*ai)}。
对整数n>t,如果F(n) != F(n-m) 则需要对F(n-m)的最优解:a1, a2, … am-1, am, 进行调整。对购买n本,能进行的调整只能是将am调整为0,将多出的(m+1)*am分散到其它的购买次数,否则的话,买n-m本书时也可以采用类似的调整,会得到更优解。根据t的定义可知调整后书的总数n满足:n <= t,这与假设n>t矛盾。
因而,对任意整数 n> max{sum(i*ai)} (1<=i<=m-1) 总有:F(n)=F(n-m)。即,对任意的买书折扣方案(不考虑所买书的具体种类数),可以通过常数次计算,得到最优解。
当m=5,ai能取的最大值:
a1 为1(但取1时,其它的ai都要取0)
a2 为2(但如果a3不为0, 2+3 => 5)
a3 为2 ( 3+3+3 => 4+5)
a4 为4
因此 t=0*1+0*2+2*3+4*4=22 即对:对任意整数n>22 都有 F(n)=F(n-5)
又由于F(5*k)=0,F(5*k-1)=F(k-1)一定成立,因而对任何一种5卷的买书折扣方案,只要计算所买书总数分别为6、7、8、11、12、13、16、17、18、21和22时的11个买法。
㈢ 考虑书的具体种类:
根据各卷要买的数目,按大小降序排列,记为:(a1, a2, … am) (a1 >= a2 >= … >= am)。
并记书的种类编号为(d1, d2, … dm)。再记折扣方案为(b1, b2, … bm)(bi为一次买i本的折扣,b1 > b2 > … > bm)。
如果最优解购买次数大于a1,则必有一次买的书没有d1,假设这次买了di,共有k次没买d1但却买了di,则对a1次每次都买了d1,买了a1本d1的同时,最多只能买(ai-k)本di,由ai <= a1,可知这a1次购买时必有k次没有购买di,这k次购买时,每次可多买一本di,相对折扣和更低。也就是说,不在a1次购买d1的书都可分摊到这a1次购买中,最终得到的相对折扣更少,这与已经是最优解矛盾,因而购买次数不大于a1。又由于要买a1本d1,每次不能买相同种类的,至少要买a1次,因而最优解购买次数为a1,即每次都要买一本d1。
若买法T:am次买m卷,am-1-am次买m-1卷,… a1-a2次买1卷,不是最优解,则与最优解相比较,必存在某本书由一次买i本,转移到一次买j本(m >= i > j >= 1,参考下面的直观图),转移的结果,组合i+j更改为(i-1)+(j+1),相对折扣改变了:bi-1 + bj+1 – (bi + bj) ,显然i=j+1时相对折扣没有改变,因而,i>j+1。最优解可由买法T,经过多次这种调整得到。若对所有的bi-1 + bj+1 – (bi + bj) (m >= i > j+1, j>=1)均大等于0,则说明买法T已经是最优解,因为对买法T的每一次调整都不会使相对折扣和减小。
对(a1, a2, a3, a4, a5),可以用下面的图形表示,5个长方形,各自的宽度表示要买的数目。纵方向的总高度就是每次要买的书的数目。对任意一种买法,如果将i次每次买了j卷,画一个宽为i,高为j的长方形,将以j=5,4,3,2,1顺序画的5个长方形合并,可得到该买法对应的状态图。对买法T:a5次买5卷,a4-a5次买4卷,… a1-a2次买1卷,将所画的5个长方形合并后再根据高度划分界线,也可得到下面的图形,也就是说买法T对应的是初始状态。取出较高层i的一部分补到较低层k(要求补完后,从上到下每层的宽度仍是递增的,这相当于进行调整i+(k-1)=>(i-1)+k),通过多次这样的操作,可以得到其它的任意一种买法。比如,第5层的的a5挖出一部分,补到第4或第3或第2层(由于只能买a1次,第一层的长度a1不能改变)。从图中可以看出,如果t=a5 – ( (a1-a2)+ (a1-a3) + (a1-a4) )>0则第5层长度至少为t,也就是说至少要买t次5卷,再加上每次必须买1本d1卷,在需要用动态规划求解时,只须用到4个变量即可,可减少计算量。
![](http://www.cppblog.com/images/cppblog_com/flyinghearts/image001.gif)
书上的折扣方案:
|
1
|
2
|
3
|
4
|
5
|
相对折扣
|
25%
|
20%
|
15%
|
5%
|
0
|
总相对折扣
|
25%
|
40%
|
45%
|
20%
|
0
|
所有的 i+j => (i-1)+(j+1) (5 >= i > j+1, j>=1)
调整前组合
|
|
调整后组合
|
相对折扣改变值
|
5+3
|
=>
|
4+4
|
-5%
|
5+2
|
4+3
|
25%
|
5+1
|
4+2
|
35%
|
4+2
|
3+3
|
30%
|
4+1
|
3+2
|
40%
|
3+1
|
2+2
|
10%
|
如果上述的所有相对折扣改变值都是非负值,那么买法T就是最优解。但是表格中有一个例外,5+3 => 4+4 这个调整使相对折扣值是减小了。由于任何其它调整的相对折扣改变值都大于5%,且都是使相对折扣值增大,因而不存在经过其它调整后再经过5+3 => 4+4调整仍能使相对折扣值减小。由于使相对折扣值变小的调整只有一个,经过这样的调整,肯定得到最优解,因而的书上的解法二在该例子上是正确的。