Money Changing Problem之一

Money Changing Problem

問題:給定許多種不同面額的錢幣,能否湊得某個價位?每種面額的錢幣都無限供應,一定夠用。

【待補簡例】【待補圖片】

Money Changing Problem的各種延伸問題

能否湊得某個價位(Money Changing Problem)、印出某個價位的其中一種湊法、印出某個價位的所有湊法、湊得某個價位的最少(多)錢幣用量(Change-Making Problem)、湊得某個價位的最少(多)錢幣種類、湊得某個價位的錢幣用量有哪幾種、湊得某個價位的湊法共有幾種(Coin Change Problem)、所有無法湊得的價位當中的最大價位(Frobenius Number)、無法湊得的價位共有幾種、在其之上每個價位都可湊得時的最小價位並限制錢幣用量(Postage Stamp Problem)。

接下來的文章將會解決其中一些問題。來吧,繼續吧!

能否湊得某個價位(Money Changing Problem)

Money Changing Problem也可稱為Equality Constrained Integer Knapsack Problem,是背包問題的一種變形:每個種類的物品有無限多個,weight為錢幣的面額大小,cost分為湊得到或湊不到兩種情況,並由加法運算改為OR運算。

Money Changing Problem在數值範圍不大時,可以利用DP解決,解法有點類似於0/1 Knapsack Problem──只是每種面額的錢幣都改為無限供應,因此recurrence稍微變動了一點點,於每一種錢幣當中,都必須考慮每一個錢幣用量。遞迴公式如下:

c(n, m) =    c(n-1, m - 0*M[n])   用去零個第n種錢幣
          or c(n-1, m - 1*M[n])   用去一個第n種錢幣
          or c(n-1, m - 2*M[n])   用去兩個第n種錢幣
          or ...                  ...

c(n, m) =
 { true                       , if n = 0 and m = 0
 { false                      , if n = 0 and m > 0
 { c(n-1, m - 0*M[n]) or ...  , if n > 0 and m-k*M[n] >= 0

n:用第1種到第n種錢幣來湊得價位。
m:欲湊得的價位值。
c(n, m):用第1種到第n種錢幣是否能湊得價位m。
M[n]:第n種錢幣的面額大小。

下面這種分割問題的方式更加簡潔。仿照0/1 Knapsack Problem的方式,以一個錢幣的去留,將原問題分割成小問題。時間複雜度是O(N*M),N為面額種類數,M為價位大小。

c(n, m) = c(n-1, m) or c(n, m-M[n])
          ^^^^^^^^^    ^^^^^^^^^^^^
          保持一樣     用去一個錢幣

c(n, m) =
 { true                       , if n = 0 and m = 0
 { false                      , if n = 0 and m > 0
 { c(n-1, m) or c(n, m-M[n])  , if n > 0 and m-M[n] >= 0
 { c(n-1, m)                  , if n > 0 and m-M[n] < 0

n:用第1種到第n種錢幣來湊得價位。
m:欲湊得的價位值。
c(n, m):用第1種到第n種錢幣是否能湊得價位m。
M[n]:第n種錢幣的面額大小。

實行DP所用的陣列,其實就是一個集合(可參考本站文件「Data Structure─Set」)。使用Bitmap取代該陣列,可以節省記憶體空間。這裡不另贅述。

也可以使用Top-down來做。採用Top-down,必須隨時記錄計算過的小問題,但是原本的bool陣列只有是和不是兩種情形,只能恰好儲存小問題的答案,而無法記錄小問題是否計算過;所以必須再宣告一個bool陣列來記錄小問題是否計算過,或者採用int陣列、以特定數值來記錄小問題是否計算過(例如正值和負值)。

能否湊得某個價位(Money Changing Problem)

這裡提供另外一種分割問題的方法。湊得一個價位可以使用任何一種錢幣,使用任何一種錢幣可以湊得一個價位:

c(m) =    c(m - M[1])   最後是用第1種錢幣
       or c(m - M[2])   最後是用第2種錢幣
       or ...           ...
       or c(m - M[n])   最後是用第n種錢幣

c(m) =
 { false                              , if m < 0
 { true                               , if m = 0
 { c(m - M[1]) or ... or c(m - M[n])  , if m > 0

m:欲湊得的價位值。
c(m):這些錢幣是否能湊得價位m。
M[n]:第n種錢幣的面額大小。

這裡是Bottom-up的程式碼。與上一個段落的程式碼做比較,可以發現兩支程式碼迴圈的層序恰好相反,非常有趣。

也可以用Top-down做。

UVa 10306 10898 10261

湊得某個價位的湊法共有幾種(Coin Change Problem)

分割問題的方法就和Money Changing Problem一樣!只是將or運算改為加法運算罷了。

c(n, m) = c(n-1, m) + c(n, m-M[n])
          ^^^^^^^^^    ^^^^^^^^^^^^
         不用這種錢幣  用去一個錢幣

c(n, m) =
 { 1                         , if n = 0 and m = 0
 { 0                         , if n = 0 and m > 0
 { c(n-1, m) + c(n, m-M[n])  , if n > 0 and m-M[n] >= 0
 { c(n-1, m)                 , if n > 0 and m-M[n] < 0

n:用第1種到第n種錢幣來湊得價位。
m:欲湊得的價位值。
c(n, m):用第1種到第n種錢幣湊得價位m的湊法數目。
M[n]:第n種錢幣的面額大小。

湊得某個價位的湊法共有幾種(Coin Change Problem)

如同Money Changing Problem,這是另一種分割問題的方法。

c(m) =   c(m - M[1])   最後是用第1種錢幣
       + c(m - M[2])   最後是用第2種錢幣
       + ...           ...
       + c(m - M[n])   最後是用第n種錢幣

c(m) =
 { 0                            , if m < 0
 { 1                            , if m = 0
 { c(m-M[1]) + ... + c(m-M[n])  , if m > 0

m:欲湊得的價位值。
c(m):這些錢幣湊得價位m的湊法數目。
W[n]:第n種錢幣的面額大小。

UVa 147 357 674 10313 430

湊得某個價位的最少錢幣用量(Change-Making Problem)

將cost改為錢幣數。如果錢幣數為無限大,則表示湊不到。越來越像0/1 Knapsack Problem了。然而各種面額的錢幣是無限供應的,並非只有零個或一個。

c(n, m) = min( c(n-1, m) , c(n, m-M[n]) + 1 )
               ^^^^^^^^^   ^^^^^^^^^^^^^^^^
               保持一樣      用去一個錢幣

n:用第1種到第n種錢幣來湊得價位。
m:欲湊得的價位值。
c(n, m):用第1種到第n種錢幣湊得價位m,最少所需要的錢幣數。
M[n]:第n種錢幣的面額大小。

湊得某個價位的最少錢幣用量(Change-Making Problem: Cashier's Algorithm)

Lena Chang, James F. Korsh. Canonical Coin and Greedy Solutions. Journal of the ACM, 1976, 23(3), 418-422.

Cashier's Algorithm採用greedy策略,一開始先用面額最大的錢幣開始湊,接著依序用面額次大的錢幣繼續湊,直到湊足該價位為止(也可能無法湊得)。這種湊法不一定能夠正確判斷能否湊得,錢幣用量也不一定是最少的,端看手頭擁有的錢幣面額是哪些。

有一個方法可驗證手頭擁有的錢幣面額,是否適合用Cashier's Algorithm找出湊得某個價位的最少錢幣用量。這是一種遞迴的驗證方式:

嘗試用最大面額的錢幣開始湊某個價位,並儘量湊足此價位;如果剩餘的價位差額可以用剩餘的錢幣面額湊得,且錢幣用量最少,則湊得原價位所需的錢幣用量最少。如果所有價位都能通過上述驗證,則表示手上的錢幣面額可以使用Cashier's Algorithm。【待補程式碼】

實做Cashier's Algorithm相當簡易。

另外也可以搭配Dynamic Programming,算出每一個價位的最少錢幣用量。這支程式碼所用的錢幣面額保證每個價位都湊得到,如果會有湊不到的情形,那就得自行修改一下程式碼。

UVa 166

湊得某個價位的錢幣用量有哪幾種

重新設計recurrence,增加一個維度,建立三維的表格,計算硬幣用量。

c(n, m, t) = c(n-1, m, t) or c(n, m-M[n], t-1)

t:錢幣用量。

問題的癥結,在於紀錄每個價位當中,每種錢幣用量到底是能湊到、抑或不能湊到,故需要第三個維度。然則第三個維度其實就是一個集合(可參考本站文件「Data Structure─Set」)。既是集合,便可用Bitmap直接取代第三個維度,並以Bitmap的特性來將演算法加速。另外,當確定錢幣用量不多時,可直接以int變數(可充作32個元素的Bit Set)或long long變數(可充作64個元素的Bitmap)來作為一個Bitmap,並利用位元運算來簡化程式碼、降低程式執行時間。這裡寫段粗略的程式碼,各位請自行參透:

這裡列出幾題可以利用上述加速手段來解決的題目。這些題目不盡然都是錢幣無限供應的問題,各位得自行轉化一下。

UVa 242 10032 10690 10930

能否湊得某個價位,但是錢幣限量供應

先前所討論的都是錢幣無限供應的情況。若是錢幣限量供應,就必須考慮每一個錢幣用量,就如同最一開始的recurrence:

c(n, m) =    c(n-1, m - 0*M[n])   用去零個第n種錢幣
          or c(n-1, m - 1*M[n])   用去一個第n種錢幣
          or c(n-1, m - 2*M[n])   用去兩個第n種錢幣
          or ...                  ...

c(n, m) =
 { true                       , if n = 0 and m = 0
 { false                      , if n = 0 and m > 0
 { c(n-1, m - 0*M[n]) or ...  , if n > 0 and m-k*M[n] >= 0

n:用第1種到第n種錢幣來湊得價位。
m:欲湊得的價位值。
c(n, m):用第1種到第n種錢幣是否能湊得價位m。
M[n]:第n種錢幣的面額大小。

還可以更有效率。【待補文字】

UVa 562 711 10064 166

Money Changing Problem之二

所有無法湊得的價位當中的最大價位(Frobenius Number)

Sebastian Böcker, Zsuzsanna Lipták. A Fast and Simple Algorithm for the Money Changing Problem. Algorithmica, 2007, 48, 413-432.

當問題給定的數值範圍不大時,便可以結合同餘理論、DP、Greedy,在多項式時間內解決這個問題,其時間複雜度是O(N*a1),N為面額種類數,a1是最小的錢幣面額值。【待補文字】