Python之动态规划（最少硬币数找零）

忘是亡心i 2022-02-19 00:29 458阅读 0赞

**完整代码：**

# 动态规划最少硬币数找零
    def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
    	for cents in range(change + 1):	#依次循环从0到所需兑换面值的每一个面值
    		coinCount = cents 			#初始化最优解为当前面值数
    		newCoin = 1 				#初始化找零硬币面值列表中的面值
    		for j in [c for c in coinValueList if c <= cents]:#在不大于要找零的硬币面值列表中循环
    			# 注：minCoins[cents - j] + 1 = cents - j的最优解 + 1(1是j的最优解，因为j为一个硬币) = cents的最优解 - j的最优解 + j的最优解 = cents的最优解，所以下一行代码的意思就是：若当前面值的最优解比上一循环(或初始)当前面值的最优解更小，则
    			if minCoins[cents - j] + 1 < coinCount:	
    				coinCount = minCoins[cents - j] + 1 #临时保存当前面值的最优解
    				# 将当前硬币面值j临时保存为当前找零面值在找零硬币面值列表中的对应值
    				newCoin = j 		
    		minCoins[cents] = coinCount #记录当前找零面值在找零最优解列表中的最优解 	
    		coinsUsed[cents] = newCoin	#记录当前找零面值在找零硬币面值列表中对应的值
    	return minCoins[change]			#返回待找零数值的最优解
    
    # 获取最终找零的硬币面值
    def printCoins(coinsUsed, change):
    	while change > 0:
    		thisCoin = coinsUsed[change]#从找零硬币面值列表中获取对应的硬币面值
    		print(thisCoin, end = '、')
    		change = change - thisCoin 	#去除该面值后继续循环获取
    
    def main():
    	amnt = 63 						#待找零面值
    	clist = [1, 5, 10, 21, 25]		#有效硬币面值列表，有序无序都可以
    	coinsUsed = [0] * (amnt + 1)	#初始化找零硬币面值列表
    	coinCount = [0] * (amnt + 1)	#初始化包含所有找零最优解的列表
    	zhao = dpMakeChange(clist, amnt, coinCount, coinsUsed)	#获取找零硬币最少个数
    	resu = "找零" + str(amnt) + "美分需要" + str(zhao) + "个硬币。"
    	print(resu)
    	print("它们是：")
    	printCoins(coinsUsed, amnt)		#获取最终找零的硬币面值
    	print("\n使用列表如下：")
    	print(coinsUsed)				#找零硬币面值列表
    	print("所有数值最优解列表如下：")
    	print(coinCount)				#包含从0到所需兑换面值的每一个面值对应的最优解
    
    main()

**结果为：**

找零63美分需要3个硬币。
    它们是：
    21、21、21、
    使用列表如下：
    [1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]
    所有数值最优解列表如下：
    [0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 1, 2, 3, 4, 1, 2, 3, 4, 5, 2, 2, 3, 4, 5, 2, 3, 4, 5, 6, 3, 3, 2, 3, 4, 3, 2, 3, 4, 5, 2, 3, 3, 4, 5, 3, 3, 4, 5, 6, 3, 4, 4, 3]