雁过无痕

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::

《编程之美》读书笔记031.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本三卷重新组合成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次。其它的买书解法,都可以从解法(a55卷,a4-a54卷,a1-a21卷),通过几个 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 >= kF(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)的定义及一次可买的书的卷数j1 <= 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 >= kF(i)=F(i-m)均成立。)

 

若要判断贪心算法(“每次尽可能买m本”)是否得到全局最优解,只要判断本数为m2*m-1时是否都符合贪心算法,而m本和2*m-1本都是一定符合的,实际上只要判断本数为m+12*m-2时是否都得到全局最优解

 

若设某次买的卷数为i1<=i<=m),则剩余n-i,根据F(n-i)是否等于F(n-i-m),可将关于i的集合,分成两部分jk,其中 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中存在某个值tF(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=mF(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),故可取等号)

购买本数为913时,都满足F(i)=F(i-5) (9<=i<=13),故i>=9时,均有 F(i)=F(i-5)。由于只有本数为8这一个例外,因而若采用贪心算法,能判断出是否将F(8)F(3)计算,从而对结果进行调整,保证结果正确。

 

性质2: 存在整数k>=m,对任意整数 n >kF(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存在上界,可以假设ti*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=5ai能取的最大值:

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)=0F(5*k-1)=F(k-1)一定成立,因而对任何一种5卷的买书折扣方案,只要计算所买书总数分别为6781112131617182122时的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,买了a1d1的同时,最多只能买(ai-k)di,由ai <= a1,可知这a1次购买时必有k次没有购买di,这k次购买时,每次可多买一本di,相对折扣和更低。也就是说,不在a1次购买d1的书都可分摊到这a1次购买中,最终得到的相对折扣更少,这与已经是最优解矛盾,因而购买次数不大于a1。又由于要买a1d1,每次不能买相同种类的,至少要买a1次,因而最优解购买次数为a1,即每次都要买一本d1

 

若买法Tam次买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个长方形合并,可得到该买法对应的状态图。对买法Ta5次买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,也就是说至少要买t5卷,再加上每次必须买1d1卷,在需要用动态规划求解时,只须用到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调整仍能使相对折扣值减小。由于使相对折扣值变小的调整只有一个,经过这样的调整,肯定得到最优解,因而的书上的解法二在该例子上是正确的。

 

posted on 2010-08-15 23:48 flyinghearts 阅读(939) 评论(0)  编辑 收藏 引用 所属分类: 算法编程之美

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理