雁過無痕

《編程之美》讀書筆記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調整仍能使相對折扣值減小。由于使相對折扣值變小的調整只有一個，經過這樣的調整，肯定得到最優解，因而的書上的解法二在該例子上是正確的。