b511: 換銅板
內容
輸入不同面值的銅板，然後輸入一個金額，將全部可能的找零方式列出。譬如有 3 種銅板面值分別是 1 元、5 元、10 元，假設要湊出 17 元，如果把找零方法表示成 “(1 元個數,5 元個數,10 元個數)”，總共會有下列幾種方法
(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)
排列順序的規則: 例如 (7,0,1) 先於 (12,1,0) 因為 7 比 12 小；而 (7,0,1) 和 (7,2,0) 的順序，因為第一個數目 7 和 7 相等，這時候就要比第二個數目，而由於 0 小於 2 所以 (7,0,1) 先於 (7,2,0)。
輸入
輸入有三行
第一行一個數字 N 代表有幾種不同面值的銅板 (N <= 5)
第二行就是 N 個整數，表示 N 種對應的銅板面值
第三行一個數字是要需要找零的金額
銅板面值和金額都是不超過 100 的正整數。（補充 by liouzhou_101）
3
1 5 10
17
輸出
列出每一種找零方法，用括號框住每個銅板的數量，數量之間用逗號隔開，每一種找零方法後面要換行。不同的找零方法的排列順序要依照題目的規定。
(2,1,1)
(2,3,0)
(7,0,1)
(7,2,0)
(12,1,0)
(17,0,0)
解題思路
把它想像成一棵樹，錢的種類數就是層數，錢的數量則是該子節點的數量，以範例測資為例就會變成 :
[] (根)
[0 1 2 ... 17] (1元 => 個這層有17節點)
[0 1 2 ... 4] (5元 => 這層有 17 * 4 = 68 個節點)
[0 1] (10元 => 這層有 68 * 2 = 136 個節點)
如果依序走訪第 2 第 3 第 0 個節點，那(2,3,0)走訪的結果就為 1 * 2 + 5 * 3 + 10 * 0 = 17 元。
由於輸出排序為
(0,0,0) → (0,0,n) → (0,n,n) → (n,n,n)
所以用前序走訪的方式來走訪整個樹，到底部時就判斷走訪的結果是否為目標值。
剪枝 :
因為每在走訪時同一層的結果只會越來越大，所以當該層的走訪結果大於目標值時，當前和其後面的節點都必大於目標值，故可直接返回上一層。
同樣以範例測資為例：
當走訪至 (10,2) 節點時，因為是採用前序走訪的方式，所以 (10,1) 和其子節點都已經走訪過了，只剩 (10,2) , (10,3) , (10,4) 沒走訪，而 (10,2) 節點結果為 1 _ 10 + 5 _ 2 = 25，超過目標值 17，而 (10 , 3) , (10 , 4) 節點又大於 (10 , 2)，也就必定大於目標值，所以可以直接返回上一層 (也就是從 (11) 開始繼續走訪 )。
Max=0
coin=[]*10
cont=[0]*10
Sum=0
lv=0
def dfs(Sum, lv):
i=0
while (Sum<m):
if (lv < Max):
dfs(Sum, lv + 1)
Sum = Sum+ coin[lv];
cont[lv]=cont[lv]+1;
i=i+1
#print(Sum,lv,i)
#print (Sum,m)
if (Sum == m):
print ('(',end='')
for i in range (len(cont)-1):
print(cont[i], ',',end='')
print (cont[i+1],') \n')
cont[lv] = 0
print ( '\n -----b511: 換銅板-----')
while True:
try:
n = int(input('數字 N 代表有幾種不同面值的銅板 (N <= 5) -->'))
coin = [int(i) for i in input(' N 個整數，表示 N 種對應的銅板面值-->').split()] # 錢幣面額
m = int(input('數字是要需要找零的金額-->')) # 總金額
cont=[0]*len(coin)
Max=n-1
print ('(',end='')
for i in range (len(cont)-1):
print(coin[i], ',',end='')
print (coin[i+1],') \n')
print ('==========')
dfs(0,0)
except:
break
>>> %Run -c $EDITOR_CONTENT
-----b511: 換銅板-----
數字 N 代表有幾種不同面值的銅板 (N <= 5) -->3
N 個整數，表示 N 種對應的銅板面值-->1 5 10
數字是要需要找零的金額-->17
(1 ,5 ,10 )
==========
(2 ,1 ,1 )
(2 ,3 ,0 )
(7 ,0 ,1 )
(7 ,2 ,0 )
(12 ,1 ,0 )
(17 ,0 ,0 )
數字 N 代表有幾種不同面值的銅板 (N <= 5) -->
>>>
沒有留言:
張貼留言