正誼百貨公司的週年慶到了，該公司推出福袋的促銷活動，除了百萬名車等大獎外，一般福袋則是由5樣商品組成，這5樣商品的價格分別是2元、5元、10元、20元、25元，每包福袋中的每種商品可以放很多個，也可以完全不放，請問以這5種商品要湊出 N 元的福袋，總共有幾種不同的組合。
輸入說明：
輸入一個正整數 N (2<=N<=1000)，代表福袋的價值。
輸出說明：
請輸出以這5種商品湊出 N 元的福袋總共有幾種不同的組合。
範例輸入：
輸入1: 10 輸入2: 20
範例輸出 ：
輸出1: 3 輸出2: 7
硬幣面值組合問題
問題描述
假設我們有8種不同面值的硬幣｛1，2，5，10，20，50，100，200｝，用這些硬幣組合夠成一個給定的數值n。例如n=200，那麼一種可能的組合方式為 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100. 問總過有多少種可能的組合方式？ (這道題目來自著名程式設計網站ProjectEuler, 點擊這裡查看原題目) 類似的題目還有：
[華為面試題] 1分2分5分的硬幣三種，組合成1角，共有多少種組合
[創新工廠筆試題] 有1分，2分，5分，10分四種硬幣，每種硬幣數量無限，給定n分錢，有多少中組合可以組成n分錢
問題分析
給定一個數值sum，假設我們有m種不同類型的硬幣{V1, V2, ..., Vm}，如果要組合成sum，那麼我們有
sum = x1 * V1 + x2 * V2 + ... +
xm * Vm
求所有可能的組合數，就是求滿足前面等值的係數{x1, x2, ..., xm}的所有可能個數。
[思路1] 當然我們可以採用暴力枚舉，各個係數可能的取值無非是x1
= {0, 1, ..., sum / V1}, x2 = {0, 1, ..., sum/ V2}等等。這對於硬幣種類數較小的題目還是可以應付的，比如華為和創新工廠的題目，但是複雜度也很高O（sum/V1 * sum/V2 * sum/V3 * ...）
[思路2] 從上面的分析中我們也可以這麼考慮，我們希望用m種硬幣構成sum，根據最後一個硬幣Vm的係數的取值為無非有這麼幾種情況，xm分別取｛0, 1, 2, ..., sum/Vm｝，換句話說，上面分析中的等式和下面的幾個等式的聯合是等價的。
sum = x1 * V1 + x2 * V2 + ... +
0 * Vm
sum = x1 * V1 + x2 * V2 + ... +
1 * Vm
sum = x1 * V1 + x2 * V2 + ... +
2 * Vm
...
sum = x1 * V1 + x2 * V2 + ... +
K * Vm
其中K是該xm能取的最大數值K = sum / Vm。可是這又有什麼用呢？不要急，我們先進行如下變數的定義：
dp[i][sum] = 用前i種硬幣構成sum 的所有組合數。
那麼題目的問題實際上就是求dp[m][sum]，即用前m種硬幣（所有硬幣）構成sum的所有組合數。在上面的聯合等式中：當xn=0時，有多少種組合呢？ 實際上就是前i-1種硬幣組合sum，有dp[i-1][sum]種！
xn = 1 時呢，有多少種組合？ 實際上是用前i-1種硬幣組合成(sum - Vm)的組合數，有dp[i-1][sum -Vm]種; xn =2呢， dp[i-1][sum - 2 * Vm]種，等等。所有的這些情況加起來就是我們的dp[i][sum]。所以：
dp[i][sum] = dp[i-1][sum - 0*Vm]
+ dp[i-1][sum - 1*Vm]
+ dp[i-1][sum - 2*Vm] + ... +
dp[i-1][sum - K*Vm]; 其中K = sum / Vm
換一種更抽象的數學描述就是：
通過此公式，我們可以看到問題被一步步縮小，那麼初始情況是什麼呢？如果sum=0，那麼無論有前多少種來組合0，只有一種可能，就是各個係數都等於0；
dp[i][0] = 1 // i = 0, 1,
2, ... , m
如果我們用二位元陣列表示dp[i][sum], 我們發現第i行的值全部依賴與i-1行的值，所以我們可以逐行求解該陣列。如果前0種硬幣要組成sum，我們規定為dp[0][sum]
= 0.
#====================================================================
# Dynamic Programming Python implementation of Coin Change problem
def count(S, m, n):
# We need n+1 rows as the table is consturcted in bottom up
# manner using the base case 0 value case (n = 0)
table = [[0 for x in range(m)] for x in range(n+1)]
# Fill the enteries for 0 value case (n = 0)
for i in range(m):
table[0][i] = 1
# Fill rest of the table enteries in bottom up manner
for i in range(1, n+1):
for j in range(m):
# Count of solutions including S[j]
x = table[i - S[j]][j] if i-S[j] >= 0 else 0
# Count of solutions excluding S[j]
y = table[i][j-1] if j >= 1 else 0
# total count
table[i][j] = x + y
return table[n][m-1]
# Driver program to test above function
arr = [2, 5, 10,20 ,25]
m = len(arr)
print("福袋則是由5樣商品組成，這5樣商品的價格分別是2元、5元、10元、20元、25元，")
print("每包福袋中的每種商品可以放很多個，")
print("也可以完全不放，請問以這5種商品要湊出 N 元的福袋，總共有幾種不同的組合。")
n = int(input("輸入一個正整數 N (2<=N<=1000)，代表福袋的價值 : "))
print("這5種商品湊出",n,"元的福袋總共有",count(arr, m, n),"種不同的組合。")
# This code is contributed by Bhavya Jain
====================== RESTART: F:/Python_APSC/b029.py ======================
福袋則是由5樣商品組成，這5樣商品的價格分別是2元、5元、10元、20元、25元，
每包福袋中的每種商品可以放很多個，
也可以完全不放，請問以這5種商品要湊出 N 元的福袋，總共有幾種不同的組合。
輸入一個正整數 N (2<=N<=1000)，代表福袋的價值 : 10
這5種商品湊出 10 元的福袋總共有 3 種不同的組合。
>>>
====================== RESTART: F:/Python_APSC/b029.py ======================
福袋則是由5樣商品組成，這5樣商品的價格分別是2元、5元、10元、20元、25元，
每包福袋中的每種商品可以放很多個，
也可以完全不放，請問以這5種商品要湊出 N 元的福袋，總共有幾種不同的組合。
輸入一個正整數 N (2<=N<=1000)，代表福袋的價值 : 20
這5種商品湊出 20 元的福袋總共有 7 種不同的組合。
>>>
====================== RESTART: F:/Python_APSC/b029.py ======================
福袋則是由5樣商品組成，這5樣商品的價格分別是2元、5元、10元、20元、25元，
每包福袋中的每種商品可以放很多個，
也可以完全不放，請問以這5種商品要湊出 N 元的福袋，總共有幾種不同的組合。
輸入一個正整數 N (2<=N<=1000)，代表福袋的價值 : 100
這5種商品湊出 100 元的福袋總共有 273 種不同的組合。
>>>
沒有留言:
張貼留言