找零兑换递归解决

背景：

假设你为宜家自动售货机厂家变成，自动售货机要每次找给顾客最少数量的硬币。如假设某次顾客投进1元纸币，买了0.37的东西，要找0.63元，那么最少数量就是：3个1分钱硬币，1个1毛钱硬币，1个5毛钱硬币

代码：

def?recMC(coin_value_li,change):
????min_coins=change
????if?change?in?coin_value_li:
????????return?1
????for?i?in?[c?for?c?in?coin_value_li?if?c?<=?change]:
????????num_coins=1+recMC(coin_value_li,change-i)
????????if?num_coins<?min_coins:
????????????min_coins=num_coins
????return?min_coins

import?time

print(time.process_time())
print(recMC([1,5,10,25],63))
print(time.process_time())

上述代码中有大量需要重复计算的步骤所以计算速度极慢。

优化代码：

通过将中间结果进行缓存，提高计算速度。

import?time

def?recDC(coin_value_li,change,known_resulsts):
????min_coins=change
????if?change?in?coin_value_li:
????????#?记录最优解
????????known_resulsts[change]=1
????????return?1
????elif?known_resulsts[change]>0:
????????return?known_resulsts[change]
????else:
????????for?i?in?[c?for?c?in?coin_value_li?if?c?<=?change]:
????????????num_coins=1+recDC(coin_value_li,change-i,known_resulsts)
????????????if?num_coins<?min_coins:
????????????????min_coins=num_coins
????????????????#?找到最优解，记录到表中
????????????????known_resulsts[change]=min_coins
????return?min_coins

print(time.process_time())
print(recDC([1,63,[0]*64))
print(time.process_time())

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!