?

---

一、題目：換錢的最小次數(shù)

? 給定數(shù)組arr,arr中所有的值都為正數(shù)且不重復(fù)。每個值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個整數(shù)aim代表要找的錢數(shù)，求組成aim的最少貨幣數(shù)。

? 舉個例子
? arr[5,2,3] ,aim=20
?　　4張5元可以組成20,并且是最小的，所以返回4
? arr[5,2,3],aim=0。
? 　　不用任何貨幣就可以組成0元，這里返回0.
? arr[5,2,3],ami=4
? 　　這里無法組成返回-1

思路：時間和空間都為O（M*aim)【len(arr) = M 】

dp 矩陣為：大小為M*aim

dp[i][j]的含義是在可以任意使用arr[0…i]貨幣的情況下，組成j所需的最小張數(shù)，矩陣的每一行和每一列可以先確定，其他的位置dp[i][j] = min( dp[i-1][j] , dp[i][j-arr[i]]+1)。

dp的第一行表示：只用 5 來分別構(gòu)成 0……20 最少要多少張，比如 5 需要 1張，10需要2張，……構(gòu)不成的賦系統(tǒng)最大值，最后返回-1。

dp的第二行表示：只用5和2分別構(gòu)成0到20 最少要多少張。

dp的第三行表示：只用5，2，3分別構(gòu)成0到20最少要多少張。

?

dp矩陣的構(gòu)建：初始化系統(tǒng)最大值

• 第一列都為0，因為0不需要任何幣來構(gòu)成。
• 第一行：能被5整除的賦值，值為整除的數(shù)。比如：5賦值1，10賦值2，15賦值3，20賦值4。
• 第二行、第三行……：

比如：dp 第2行第7列的值 2 是根據(jù)

dp [7-2] +1 = 1 +1 =2來的，即【7可以由1個5和1個2組成】，

但是還要看第一行7列的值是不是更小，即 dp [i][j] = min(?dp [j-arr[i]] +1，dp [i-1][j] ），dp [j-arr[i]] +1不能是系統(tǒng)最大值。

?代碼1：

import sys def minCoins1(arr, aim):if arr == None or len(arr) == 0 or aim < 0:return -1row = len(arr)dp = [[sys.maxsize for i in range(aim+1)] for j in range(row)]for i in range(row):dp[i][0] = 0for j in range(1, aim+1):if j % arr[0] == 0:dp[0][j] = j // arr[0]for i in range(1, row):for j in range(1, aim+1):left = sys.maxsizeif j - arr[i] >= 0 and dp[i][j-arr[i]] != sys.maxsize:left = dp[i][j-arr[i]] + 1dp[i][j] = min(left, dp[i-1][j])return dp[row-1][aim] if dp[row-1][aim] != sys.maxsize else -1 arr = [5,2,3] aim = 20 minCoins1(arr, aim)

?代碼2：時間為O（M*aim)【len(arr) = M 】，空間為O（aim+1)，dp 大小為 aim+1的列表

#經(jīng)過空間壓縮的動態(tài)規(guī)劃 def minCoins2(arr, aim):if arr == None or len(arr) == 0 or aim < 0:return -1row = len(arr)dp = [sys.maxsize for i in range(aim+1)]dp[0] = 0for i in range(1, aim+1):if i % arr[0] == 0:dp[i] = i // arr[0]for i in range(1, row):dp[0] = 0for j in range(1, aim+1):left = sys.maxsizeif j - arr[i] >= 0 and dp[j-arr[i]] != sys.maxsize:left = dp[j-arr[i]] + 1dp[j] = min(left, dp[j])return dp[aim] if dp[aim] != sys.maxsize else -1

?

---

題目二：換錢的方法數(shù)

https://blog.csdn.net/qq_34342154/article/details/77122125

給定數(shù)組arr，arr中所有的值都為整數(shù)且不重復(fù)。每個值代表一種面值的貨幣，每種貨幣有無數(shù)張，再給定一個整數(shù)aim代表要找的錢數(shù)，求換錢的方法有多少種。

思路1：暴力遞歸，最壞情況下時間O(aim^N)，N表示數(shù)組的長度

首先介紹暴力遞歸的方法。如果arr = [5, 10, 25, 1]，aim = 1000，分析過程如下：
用０張５元的貨幣，讓[10, 25, 1]組成剩下的1000，最終方法數(shù)記為res1。
用１張５元的貨幣，讓[10, 25, 1]組成剩下的995，最終方法數(shù)記為res2。
用２張５元的貨幣，讓[10, 25, 1]組成剩下的990，最終方法數(shù)記為res3。
……
用201張５元的貨幣，讓[10, 25, 1]組成剩下的0，最終方法數(shù)記為res201。
那么res1 + res2 + res3 + …… +res201的值就是中的方法數(shù)。

?

#暴力遞歸方法 def coins1(arr, aim):def process1(arr, index, aim):if index == len(arr):return 1 if aim == 0 else 0else:res = 0for i in range(0, aim//arr[index]+1):res += process1(arr, index+1, aim-arr[index]*i)return resif arr == None or len(arr) == 0 or aim < 0:return 0return process1(arr, 0, aim)

思路2：記憶搜索：時間復(fù)雜度為O(N*aim^2)，空間復(fù)雜度O(N*aim)。

采用一個字典存儲計算過的結(jié)果，暴力遞歸會重復(fù)計算結(jié)果。比如使用0張5元+1張10元的情況和使用2張5元+0張10元的情況，都需要求[25, 1]組成剩下的990的方法數(shù)。記憶搜索就是使用一張記錄表將遞歸過程中的結(jié)果進行記錄，當下次再遇到同樣的遞歸過程，就直接使用表中的數(shù)據(jù)。

?

第三行：圈出的

第一步：當0個5：當0個2，只用【3】構(gòu)成15的方法：1個

　　　　　　　　　1個2，只用【3】構(gòu)成13的方法：-1個【不可能】

　　　　　　　　　2個2，……

　　　　　　　　　……

　　　　　　　　　7個2……

第三行：圈出的

第二步：當1個5時，當0個2，只用【3】構(gòu)成10：-1個

　　　　　　　　　 ?? 1個2，只用【3】構(gòu)成8：-1個

　　　　　　　　　　……

　　　　　　　　　　5個2，只用【3】構(gòu)成0：1個

第二行：

當0個5時：只用【2，3】構(gòu)成15有3種方法

當1個5時：只用【2，3】構(gòu)成10有2種方法

當2個5時：只用【2，3】構(gòu)成5有1種方法

當3個5時：只用【2，3】構(gòu)成0有1種方法

?

第一行：結(jié)果，用【5，2，3】構(gòu)成15有7種方法

?代碼：

def coins2(arr, aim):def process2(arr, index, aim, records):if index == len(arr):return 1 if aim == 0 else 0else:res = 0for i in range(0, aim//arr[index]+1):mapValue = records[index+1][aim-arr[index]*i]if mapValue != 0:res += mapValue if mapValue != -1 else 0else:res += process2(arr, index+1, aim-arr[index]*i, records)records[index][aim] = -1 if res == 0 else resreturn resif arr == None or len(arr) == 0 or aim < 0:return 0records = [[0 for i in range(aim+1)] for j in range(len(arr)+1)]return process2(arr, 0, aim, records) arr = [5,2,3] aim = 15 res1 = coins2(arr,aim)

?思路3：動態(tài)規(guī)劃：時間O（M*aim^2)，空間O（M*aim）

?

為何綠圈等于上一行紅圈的加和？即num += dp[i-1][j-arr[i]*k]

比如綠圈的第二行第5列那個1：只用【5，2】

上一行紅圈表示只用【5】構(gòu)成0，2，4的方法數(shù)為1，0，0

則當用0個2時，對應(yīng)【5】構(gòu)成4方法數(shù)為0

當用1個2時，對應(yīng)【5】構(gòu)成2方法數(shù)為0

當2個2時，對應(yīng)【5】構(gòu)成0方法數(shù)為1

代碼：

def coins3(arr, aim):if arr == None or len(arr) == 0 or aim < 0:return 0row = len(arr)dp = [[0 for i in range(aim+1)]for j in range(row)]for i in range(row):dp[i][0] = 1for j in range(1, aim//arr[0]+1):dp[0][arr[0]*j] = 1for i in range(1, row):for j in range(1, aim+1):num = 0for k in range(j//arr[i]+1):num += dp[i-1][j-arr[i]*k]dp[i][j] = numreturn dp[row-1][aim]

思路4：動態(tài)規(guī)劃時間的優(yōu)化：時間O（M*aim)，空間O（M*aim）

思路3中的第三步循環(huán)k可省略。

for k in range(j//arr[i]+1):
? ? ? ? ? num += dp[i-1][j-arr[i]*k] 即

dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]] + dp[i-1][j-2*arr[i]] + …dp[i-1][j-k*arr[i]]

等價于

dp[i][j] = dp[i-1][j] + dp[i][j-arr[i]]

代碼：

def coins4(arr, aim):if arr == None or len(arr) == 0 or aim < 0:return 0row = len(arr)dp = [[0 for i in range(aim+1)] for j in range(row)]for i in range(row):dp[i][0] = 1for j in range(1, aim//arr[0]+1):dp[0][arr[0]*j] = 1for i in range(1,row):for j in range(1, aim+1): dp[i][j] = dp[i-1][j]dp[i][j] += dp[i][j-arr[i]] if j-arr[i] >= 0 else 0return dp[row-1][aim]

思路5：動態(tài)規(guī)劃空間的優(yōu)化：時間O（M*aim)，空間O(aim)。

def coin5(arr,aim):if not arr or not aim:return 0dp = [0] * (aim + 1)for i in range(0,aim+1,arr[0]):dp[i] = 1for i in range(1,len(arr)):for j in range(1,aim+1):dp[j] += dp[j-arr[i]] if j - arr[i] >= 0 else 0return dp[-1] arr = [5,2,3] aim = 15 coin5(arr,aim)

?

---

題目三、0-1背包

m個物品價值為 p[m]，體積為 w[m]，現(xiàn)有一個容量為 v 的背包，怎么裝物品價值最大?

思路：

m[i][j] = max{m[i - 1][j], m[i - 1][j - w[i]] + v[i]}???? j >= w[i];???????????

? ? ? ?? = m[i - 1][j]??????????????????????????????????????????????????? j < w[i];

解釋：

當我們依次從package 里面取到第 i 個物品的時候，我們可以在前 i 個物品中，得到一個最優(yōu)解。而每一次遍歷，如下
如果當前物品大于背包的容積，這個物品太大了，包塞不下。那么最優(yōu)解就是前n-1件物品放進這個背包的最大價值。
arr[i][j] = arr[i-1][j]
如果當前物品不大于背包的容積，這個物品可以塞下，需要重新開始計算，當前 i 物品組合的最大價值。分為兩種情況，該物品放還是不放。
2.1?不放的話，和上面的公式相同；?
2.2?放的話，則背包容量減去第n件物品的重量，再去裝前 i-1 件物品，所得的最大價值。兩種情況中較大的就是最優(yōu)解。
arr[i][j] = max (arr[i-1][j] , arr[i-1][j -v[i]]+ cost[j])

題目四：硬幣翻轉(zhuǎn)

有 N 個硬幣，一開始全部正面朝上，每次可以翻轉(zhuǎn) M 個硬幣（ M 小于 N ），使得最終所有硬幣反面朝上。

輸入：2 1

輸出：

2 0
1 1
0 2

輸入：5 3

5 0
2 3
1 4
4 1
3 2
0 5

輸入：5 5

5 0

0 5

輸入：5 4

No Solution

思路：

　　采用【1，1，1，1……】來作為硬幣正面，反面就變?yōu)?，每M個就變?yōu)?。

代碼：

　　

def test(N,M):arr = [1] * Nif not M % 2:print('No Solution')else:index = 0while 1 in arr:num1 , num2 = 0 , 0for i in range(len(arr)):if arr[i] == 1:num1 += 1num2 = N - num1print(num1,num2)end = index + M - N if (index + M - N)>0 else (index + M)if index <= end:for i in range(index,end):arr[i] = 1- arr[i]else:for i in range(0,end):arr[i] = 1-arr[i]for i in range(index,N):arr[i] = 1-arr[i]index = endprint(0,N) N , M = input().split() N,M = int(N),int(M) test(N,M)

?

轉(zhuǎn)載于:https://www.cnblogs.com/Lee-yl/p/9965830.html

總結(jié)

以上是生活随笔為你收集整理的算法53----换钱的最小次数和方法数【动态规划】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。