資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學使用給定硬幣獲得n盧比的方法的Python程式
假設我們有面值為(1, 2, 5和10)的硬幣。我們必須找到使用這些面值可以排列n的多少種方法。我們有一個名為count的包含4個元素的陣列，其中count[0]表示1的硬幣數量，count[1]表示2的硬幣數量，以此類推。
因此，如果輸入類似於n = 27 count = [8,4,3,2]，則輸出將為18，因此有18種可能的組合，其中一些是
10*2 + 5*1 + 2*1 = 27
10*2 + 2*3 + 1*1 = 27
10*1 + 5*3 + 2*1 = 27
10*1 + 5*1 + 4*2 + 4*1 = 27
等等…
為了解決這個問題，我們將遵循以下步驟：
- denom := [1,2,5,10]
- A := 一個大小為(n + 1)並填充0的陣列
- B := 從A建立的一個新列表
- 對於範圍從0到(count[0]和n的最小值)的i，執行：
- A[i] := 1
- 對於範圍從1到3的i，執行：
- 對於範圍從0到count[i]的j，執行：
- 對於範圍從0到n + 1 - j *denom[i]的k，執行：
- B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
- 對於範圍從0到n + 1 - j *denom[i]的k，執行：
- 對於範圍從0到n的j，執行：
- A[j] := B[j]
- B[j] := 0
- 對於範圍從0到count[i]的j，執行：
- 返回A[n]
示例
讓我們看看下面的實現以更好地理解
denom = [1,2,5,10] def solve(n, count): A = [0 for _ in range(n+1)] B = list(A) for i in range(min(count[0], n) + 1): A[i] = 1 for i in range(1, 4): for j in range(0, count[i] + 1): for k in range(n + 1 - j *denom[i]): B[k + j * denom[i]] += A[k] for j in range(0, n + 1): A[j] = B[j] B[j] = 0 return A[n] n = 27 count = [8,4,3,2] print(solve(n, count))
輸入
27, [8,4,3,2]
輸出
18
更新於：2021年10月12日
373 次檢視
廣告