python换零钱_Python算法之零钱兑换问题的解法

比如：顾客购物买37元东西，给了100元，要找63元，那最少数量就是1张50元，1张10元，3张1元，一共4张。

方法一： 贪心策略

解决这个问题，最直观的就是使用贪心策略。我们会从最大面值的钱开始，用最多的数量。有余额再到下一个最大面值，还用最多的数量，一直到1元为止。

def chage_give(coins_list, change):

solutions = []

s_list = sorted(coins_list, reverse=True)

for coin in s_list:

coins_num = change // coin

solutions += [coin,] * coins_num

change = change - coin * coins_num

if coins_num < 0:

break

return len(solutions)

if __name__ == "__main__":

print(chage_give([1, 5, 10, 20, 50, 100], 63))

运行程序，输出打印结果：

>>> 5

贪心策略在人民币的体系下表现还好，但是如果当存在有21元的面值，贪心策略就会失效。因为63元的最优解是3个面值21元。

方法二：递归调用的方式求解

既然贪心策略在特殊的面值下会失效，那我们用递归解决这个问题吧。

递归的三个首先条件，我们先确定基本结束条件：剩余需要兑换的零钱正好等于某面值。例如找零10元，答案就是1张10元。

其次是缩小问题的规模：

找零减去 1元 后， 求兑换零钱的最少数量(递归调用自身);

找零减去 5元 后， 求兑换零钱的最少数量;

找零减去 10元后， 求兑换零钱的最少数量;

找零减去 20元后， 求兑换零钱的最少数量;

找零减去 50元后， 求兑换零钱的最少数量;

上述 5项 中选择最小的一个

def change_give_recursion(coins_list, change):

min_coins = change

# 当要兑换的零钱的值正好等于面值列表中其中一项，就直接返回 1

if change in coins_list:

return 1

else:

# 对各种面值都试用递归调用自身，但选择数量最小的一个。

for i in [ c for c in coins_list if c < change]:

coin_num = 1 + change_give_recursion(coins_list, change - i)

if coin_num < min_coins:

min_coins = coin_num

return min_coins

if __name__ == "__main__":

print(change_give_recursion([1, 5, 10, 20, 50, 100], 63))

运行程序，输出打印结果：

>>> 5

上面递归解法虽然能解决问题，但最大的问题是：非常低效！例如对63元的兑换问题需要进行6千多万的递归调用，有太多的重复计算。所以优化这个算法，我们需要消除重复的计算。

我们可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过。这个算法的中间结果就是部分找零的最优解，在递归调用之前先查找表中是否已有部分找零的最优解，如果有，直接返回最优解而不进行递归调用，如果没有，才进行递归调用。

既然存在问题，我们就要做改进，改进后如下：

def change_give_recursion(coins_list, change, known_result):

min_coins = change

if change in coins_list:

# 如果兑换的零钱正好等于其中一个币值，就先将这个结果记录下来

known_result[change] = 1

return 1

elif known_result[change] > 0: # 如果已经存在这个零钱值的结果记录就直接返回

return known_result[change]

else:

for i in [ c for c in coins_list if c < change]:

coin_num = 1 + change_give_recursion(coins_list, change - i, known_result)

if coin_num < min_coins:

min_coins = coin_num

# 将得到的结果保存下来，后面调用是供之后检查

known_result[change] = min_coins

return min_coins

if __name__ == "__main__":

print(change_give_recursion([1, 5, 10, 20, 50, 100], 63, [0] * 64))

改进后的解法，极大的减少了递归调用次数。对63元的兑换问题仅需要进行221次的递归调用，是改进前的三十万分之一。这种中间结果记录的方法叫做“memoization”（记忆化/函数值缓冲）技术，提高了递归解法的性能，这种方法的应用如缓冲。

方法三：动态规划解法

动态规划（Dynamic programming，简称DP）主要用来解决一些希望找到问题最优解的优化问题

找零兑换的动态规划算法从最简单的“1元钱找零”的最优解开始，逐步递加上去，直到我们需要的找零数。在找零递加的过程中，设法保持每一分钱的递加都是最优解，一直加到求解找零数，自然得到最优解。

递加的过程能保持最优解的关键是，其依赖于更少钱数最优解的计算，而更少钱数的最优解已经得到了。问题的最优解包含了更小规模子问题的最优解，这是一个最优化问题能够用动态规划策略解决的必要条件。

计算11分钱的兑换法，我们做如下几步：

1、减去1分钱，剩下10分钱查表最优解是1

2、然后减去5分钱，剩下6分钱查表最优解是2

3、最后减去10分钱，剩下1分钱查表最优解是1

通过上述最小值得到最优解：2个硬币

def change_give_dynamic(coins_list, change, min_coins):

for cents in range(1, change + 1):

coins_count = cents

for j in [c for c in coins_list if c < cents]:

if min_coins[cents - j] + 1 < coins_count:

coins_count = min_coins[cents - j] + 1

min_coins[cents] = coins_count

return min_coins[change]

if __name__ == "__main__":

print(change_give_dynamic([1, 5, 10, 20, 50, 100], 63, [0] * 64))