动态规划: 找零问题
问题描述
现实生活中经常遇到找零钱的问题。假设去超市购物买了一个售价为3毛7分的商品，你给售货员1元（1元 = 100分）钱，售货员需要找钱给你。假设有四种面额的硬币：1分、5分、1毛、5毛，每种硬币的数量充足。现在要求售货员使用最少数量的硬币， 求出这个最少数量是多少。
也就是求一个数63，可以由集合 {1 , 5 ,10 ,50 }中任意元素任意数量组成，求最少数量。
求解思路
- 思路一：根据日常生活经验，我们找零时候会从面额最大的开始凑，如找63元，会先选择50元，然后选10元，最后选3个1元。但这个方法并不能保证零钱的数量最少。例如，假设零钱面额为{1,20,50},需要找的是60，按照刚才的方法，先选50，然后选10个1，零钱的数量为10。但是最优解却是选3个20。
- 思路二：以上方法为贪心算法，每次计算局部解只选择一条路径来计算。 为了求最优解则会遍历所有的计算路径，因此使用动态规划来求解比较合适。
首先找出子问题。
例如为了凑足零钱63，需要求解的子问题有 62(63 -1),58(63 -5) , 53(63 -10) 13(63 -50)的最少硬币数量。然后取其中最少的那个解。
需要找的零钱数量为amount , 硬币面额为 coins {c1,c2,c3...cN }。
最少硬币数量递推方程为 :
m(x) = min{m(x-ci)+1 } x-ci>=0
m(0) = 0
m(1) = 1
讲完思路后上代码。
递归程序
使用递归来写这个程序比较简单。
- 找出递归基的临界状态。
- 利用刚才递推方程递归调用选择最优解。
def rec_min_coins(amount,coins):
min_ret = amount
if not coins:
return 0
if amount ==1:
return 1
if amount <= 0:
return 0
else:
for c in coins:
if amount >= c:
min_count = rec_min_coins(amount-c,coins)+1
if min_count < min_ret: #选出最小的结果
min_ret = min_count
return min_ret
values = [1,5,10,25]
import time
start = time.time()
print(rec_min_coins(63,values))
end = time.time()
print(end-start)
out:6 104.87529873847961
运行递归程序耗费了104秒，中间一度还以为程序死循环了。
经过分析以上程序时间复杂度为O(n)=4^n 也就是4^63，可想而知其性能是多么糟糕，下面通过动态规划来优化性能。
动态规划程序
用动态规划方法，从状态0开始计算并且把结果保存到一个数组里面，以避免子问题重复计算。
def dp_min_coins(amount,coins):
mins = [0 for x in range(amount+1)]
for i in range(1,amount+1):
min_ret = i
for c in coins:
if i >=c:
min_count =mins[i-c]+1
if min_count < min_ret:
min_ret = min_count
mins[i] = min_ret
return mins[amount]
values = [1,5,10,25]
import time
start = time.time()
print(dp_min_coins(63,values))
end = time.time()
print(end-start)
out:6
0.0010821819305419922
可以看到动态规划运行时间不到1秒。
总结
遇到求最优解问题时，通常可以用动态规划或者递归来求解。但由于递归法求解过程中需要计算大量重复的子问题 ，其时间复杂度 O(n)=C^n。因此往往会优先采用性能更好的动态规划法。
