雁过无痕

《编程之美》读书笔记03： 1.4 买书问题

 

问题：

    在节假日的时候，书店一般都会做促销活动。由于《哈利波特》系列相当畅销，店长决定通过促销活动来回馈读者。在销售的《哈利波特》平装本系列中，一共有五卷，用编号0, 1, 2, 3, 4来表示。假设每一卷单独销售均需要8欧元。如果读者一次购买不同的两卷，就可以扣除5%的费用，三卷则更多。假设具体折扣的情况如下：

本数	折扣
2	5%
3	10%
4	20%
5	25%

 

在一份订单中，根据购买的卷数以及本书，就会出现可以应用不同折扣规则的情况。但是，一本书只会应用一个折扣规则。比如，读者一共买了两本卷一，一本卷二。那么，可以享受到5%的折扣。另外一本卷一则不能享受折扣。如果有多种折扣，希望能够计算出的总额尽可能的低。

要求根据这样的需求，设计出算法，能够计算出读者所购买一批书的最低价格。

 

书中给出的解法：

如果要买的书为（Y₁, Y₂, Y₃, Y₄, Y₅）（其中Y₁>=Y₂>=Y₃>=Y₄>=Y₅），贪心策略建议我们买Y₅本五卷的，Y₄-Y₅本四卷,Y₃-Y₄本三卷,Y₂-Y₃本两卷和Y₁-Y₂本一卷。由于贪心策略的反例，我们把K本五卷和K本三卷重新组合成2×K本四卷（K = min{Y5, Y3-Y4}）。结果就是我们买Y5-K本五卷的，Y₄-Y₅本四卷,Y₃-Y₄-K本三卷，Y₂-Y₃本两卷和Y₁-Y₂本一卷（K = min{Y₅, Y₃-Y₄}）。比如我们要买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本时的状态(a₁, a₂, a₃, a₄, a₅)（递减排列）。可以证明，最优解的买书次数必然是a₁次。其它的买书解法，都可以从解法（a₅次5卷，a₄-a₅次4卷，…，a₁-a₂次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本的最优解中，共有a_i次每次买了i本书，则a_i必定小于m，否则，a_i次买i本，可以优化为i次买m本和a_i-m次买i本。另外，必有a_i <= i，否则，设j=a_i > i，则j次每次买i本书，可以优化为i次每次买j本书。由于a_i存在上界，可以假设t为i*a_i(1<=i<=m-1)所有可能的乘积和中最大的，即t=max{sum(i*a_i)}。

    对整数n>t，如果F(n) != F(n-m) 则需要对F(n-m)的最优解：a₁, a₂, … a_m-1, a_m, 进行调整。对购买n本，能进行的调整只能是将a_m调整为0，将多出的(m+1)*a_m分散到其它的购买次数，否则的话，买n-m本书时也可以采用类似的调整，会得到更优解。根据t的定义可知调整后书的总数n满足：n <= t，这与假设n>t矛盾。

因而，对任意整数 n> max{sum(i*a_i)} (1<=i<=m-1) 总有：F(n)=F(n-m)。即，对任意的买书折扣方案（不考虑所买书的具体种类数），可以通过常数次计算，得到最优解。

 

当m=5，a_i能取的最大值：

a₁ 为1（但取1时，其它的a_i都要取0）

a₂ 为2（但如果a₃不为0， 2+3 => 5）

a₃ 为2  ( 3+3+3 => 4+5)

a₄ 为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个买法。

 

㈢ 考虑书的具体种类：

根据各卷要买的数目，按大小降序排列，记为：(a₁, a₂, … a_m) (a₁ >= a₂ >= … >= a_m)。

并记书的种类编号为(d₁, d₂, … d_m)。再记折扣方案为(b₁, b₂, … b_m)（b_i为一次买i本的折扣，b₁ > b₂ > … > b_m)。

如果最优解购买次数大于a₁，则必有一次买的书没有d₁，假设这次买了d_i，共有k次没买d₁但却买了d_i，则对a₁次每次都买了d₁，买了a₁本d₁的同时，最多只能买(a_i-k)本d_i，由a_i <= a₁，可知这a₁次购买时必有k次没有购买d_i，这k次购买时，每次可多买一本d_i，相对折扣和更低。也就是说，不在a₁次购买d₁的书都可分摊到这a₁次购买中，最终得到的相对折扣更少，这与已经是最优解矛盾，因而购买次数不大于a₁。又由于要买a₁本d₁，每次不能买相同种类的，至少要买a₁次，因而最优解购买次数为a₁，即每次都要买一本d₁。

 

若买法T：a_m次买m卷，a_m-1-a_m次买m-1卷，… a₁-a₂次买1卷，不是最优解，则与最优解相比较，必存在某本书由一次买i本，转移到一次买j本(m >= i > j >= 1，参考下面的直观图)，转移的结果，组合i+j更改为(i-1)+(j+1)，相对折扣改变了：b_i-1 + b_j+1 – (b_i + b_j) ，显然i=j+1时相对折扣没有改变，因而，i>j+1。最优解可由买法T，经过多次这种调整得到。若对所有的b_i-1 + b_j+1 – (b_i + b_j) （m >= i > j+1, j>=1）均大等于0，则说明买法T已经是最优解，因为对买法T的每一次调整都不会使相对折扣和减小。

 

对(a₁, a₂, a₃, a₄, a₅)，可以用下面的图形表示，5个长方形，各自的宽度表示要买的数目。纵方向的总高度就是每次要买的书的数目。对任意一种买法，如果将i次每次买了j卷，画一个宽为i，高为j的长方形，将以j=5,4,3,2,1顺序画的5个长方形合并，可得到该买法对应的状态图。对买法T：a₅次买5卷，a₄-a₅次买4卷，… a₁-a₂次买1卷，将所画的5个长方形合并后再根据高度划分界线，也可得到下面的图形，也就是说买法T对应的是初始状态。取出较高层i的一部分补到较低层k（要求补完后，从上到下每层的宽度仍是递增的，这相当于进行调整i+(k-1)=>(i-1)+k），通过多次这样的操作，可以得到其它的任意一种买法。比如，第5层的的a₅挖出一部分，补到第4或第3或第2层（由于只能买a₁次，第一层的长度a₁不能改变）。从图中可以看出，如果t=a₅ – ( (a₁-a₂)+ (a₁-a₃) + (a₁-a₄) )>0则第5层长度至少为t，也就是说至少要买t次5卷，再加上每次必须买1本d₁卷，在需要用动态规划求解时，只须用到4个变量即可，可减少计算量。

书上的折扣方案：

	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调整仍能使相对折扣值减小。由于使相对折扣值变小的调整只有一个，经过这样的调整，肯定得到最优解，因而的书上的解法二在该例子上是正确的。