东莞网站建设销售公司,务川县住房和城乡建设局网站,长春个人网站制作公司,深圳网站建设推荐refer:http://interactivepython.org/courselib/static/pythonds/index.html 1. 问题描述 Tom在自动售货机上买了一瓶饮料#xff0c;售价37美分#xff0c;他投入了1美元#xff08;1美元 100美分#xff09;#xff0c;现在自动售货机需要找钱给他。售货机中现在只有四… refer:http://interactivepython.org/courselib/static/pythonds/index.html 1. 问题描述 Tom在自动售货机上买了一瓶饮料售价37美分他投入了1美元1美元 100美分现在自动售货机需要找钱给他。售货机中现在只有四种面额的硬币1美分、5美分、10美分、25美分每种硬币的数量充足。现在要求使用最少数量的硬币给Tom找钱求出这个最少数量是多少。 2. 问题分析 自动售卖机需要给Tom找零钱63美分而售卖机中只有四种面额的硬币可以使用现在的核心问题就是如何用四种面额的硬币来凑够63美分并且使用的硬币数量最少。 现在我们换个角度来思考这个问题 是不是可以将问题规模先缩小比如我不知道凑够63美分最少需要多少个硬币那凑够1美分、2美分的方案则显而易见是可以马上知道的。 为了后面叙述方便用f(i) n这个等式来表示这样一种含义凑够i美分0 i 63所需要的最少硬币数量为n个那么我们从凑够0美分开始写 凑0美分因为0美分根本不需要硬币因此结果是0f(0) 0凑1美分因为有1美分面值的硬币可以使用所以可以先用一个1美分硬币然后再凑够0美分即可而f(0)的值是我们已经算出来了的所以f(1) 1 f(0) 1 0 1这里f(1) 1 f(0) 中的1表示用一枚1美分的硬币凑2美分此时四种面额的硬币中只有1美分比2美分小所以只能先用一个1美分硬币然后再凑够1美分即可而f(1)的值我们也已经算出来了所以f(2) 1 f(1) 1 1 2这里f(2) 1 f(1) 中的1表示用一枚1美分的硬币凑3美分和上一步同样的道理f(3) 1 f(2) 1 2 3凑4美分和上一步同样的道理f(4) 1 f(3) 1 3 4凑5美分这时就出现了不止一种选择了因为有5美分面值的硬币。方案一使用一个5美分的硬币再凑够0美分即可这时f(5) 1 f(0) 1 0 1这里f(5) 1 f(0) 中的1表示用一枚5美分的硬币方案二使用1个1美分的硬币然后再凑够4美分此时f(5) 1 f(4) 1 4 5。综合方案一和方案二可得f(5) min{1 f(0),1 f(4)} 1凑6美分此时也有两种方案可选方案一先用一个1美分然后再凑够5美分即可即f(6) 1 f(5) 1 1 2方案二先用一个5美分然后再凑够1美分即可即f(6) 1 f(1) 1 1 2。综合两种方案有f(6) min{1 f(5), 1 f(1)} 2...省略从上面的分析过程可以看出要凑够i美分就要考虑如下各种方案的最小值 1 f(i - value[j])其中value[j]表示第j种j从0开始0 j 4面值且value[j] i 那么现在就可以写出状态转移方程了 f(i) 0, i 0 f(i) 1, i 1 f(i) min{1 f(i - value[j])}, i 1value[j] i 3. Talk is cheap, show the code 1. 基本版 # coding:utf-8
# 找零钱问题算法实现基本版# 4种硬币面值
values [1,5,10,25]# 凑够amount这么多钱数需要的最少硬币个数
def minCoins(amount):# 需要的最少硬币个数ret_min amountif amount 1:ret_min 0# 如果要找的钱数恰好是某种硬币的面值那么最少只需一个硬币elif amount in values:ret_min 1else:# 遍历面值数组中面值小于等于amount的那些元素for v in [x for x in values if x amount]:# 用面值为v的硬币其他硬币找零所需的最少硬币数min_num 1 minCoins(amount - v)# 判断min_num和ret_min的大小更新ret_minif min_num ret_min:ret_min min_numreturn ret_mindef main():print minCoins(63)main() 将上面脚本保存成coins.py文件在ipython中执行%time %run coins.py得到的结果如下 6 CPU times: user 1min 45s, sys: 0 ns, total: 1min 45s Wall time: 1min 45s 分析可以看出在我的电脑上仅仅是为了计算用4种面额找63美分零钱就耗时1分钟45秒105秒这是无法忍受的。那么究竟为什么耗时这么巨大下面对代码稍加改造进行一下性能分析。 2. 性能分析 # coding:utf-8
# 找零钱问题算法实现基本版性能分析# 统计递归次数
recursion_num 0# 4种硬币面值
values [1,5,10,25]# 凑够amount这么多钱数需要的最少硬币个数
def minCoins(amount):global recursion_num# 需要的最少硬币个数ret_min amountif amount 1:ret_min 0# 如果要找的钱数恰好是某种硬币的面值那么最少只需一个硬币elif amount in values:ret_min 1else:# 遍历面值数组中面值小于等于amount的那些元素for v in [x for x in values if x amount]:# 用面值为v的硬币其他硬币找零所需的最少硬币数min_num 1 minCoins(amount - v)# 判断min_num和ret_min的大小更新ret_minif min_num ret_min:ret_min min_numrecursion_num 1return ret_mindef main():print minCoins(63)print recursion_nummain() 将上面脚本保存成coins.py文件在ipython中执行%time %run coins.py得到的结果如下 6 67716925 CPU times: user 2min, sys: 36 ms, total: 2min Wall time: 2min 分析可见minCoins函数一共被递归调用了67716925次真是难以想象为了计算最多64个函数值amount取0~63居然递归调用了函数minCoins 67716925次平均求每个值调用了1058076次。那么问题出在哪里了呢出在了重复计算上有很多值被重复计算了上百万次。那么如何尽量减少重复计算呢下面用一个缓存数组来缓存每次求出的函数值供后面使用从而减少重复计算。 3. 性能优化版 # coding:utf-8
# 找零钱问题算法实现基本版性能分析# 统计递归次数
recursion_num 0# 4种硬币面值
values [1,5,10,25]# 缓存数组为一个一维数组用于缓存每次递归函数求得的值
# cache[i]表示凑够i美分所需的最少硬币个数cache的元素都被初始化为-1表示个数未知
cache []# 初始化缓存数组
def init(amount):global cachecache [-1] * (amount 1)# 凑够amount这么多钱数需要的最少硬币个数
def minCoins(amount):global recursion_numglobal cache# 需要的最少硬币个数ret_min amount# 如果缓存数组中有对应的值那么直接从中取不再重复计算了if cache[amount] ! -1:ret_min cache[amount]elif amount 1:ret_min 0# 如果要找的钱数恰好是某种硬币的面值那么最少只需一个硬币elif amount in values:ret_min 1else:# 遍历面值数组中面值小于等于amount的那些元素for v in [x for x in values if x amount]:# 用面值为v的硬币其他硬币找零所需的最少硬币数min_num 1 minCoins(amount - v)# 判断min_num和ret_min的大小更新ret_minif min_num ret_min:ret_min min_num# 更新缓存数组cache[amount] ret_minrecursion_num 1return ret_mindef main():init(63)print minCoins(63)print cacheprint recursion_nummain() 将上面脚本保存成coins.py文件在ipython中执行%time %run coins.py得到的结果如下 6 [-1, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6] 206 CPU times: user 4 ms, sys: 0 ns, total: 4 ms Wall time: 2.2 ms 分析可见cache数组除了cache[0]没被用到以外其他元素都被利用到了利用率还是很高的。使用缓存数组后minCoins函数的递归调用次数从67716925次降低到了206次降低了328722倍程序耗时从105秒降低到了2.2ms降低了47727倍优化效果是巨大的。 上一篇动态规划之金矿模型中也使用到了缓存数组优化效果也是巨大的在本文中又一次看到了动态规划中缓存数组的重要性。 转载于:https://www.cnblogs.com/jiayongji/p/7118895.html
