数据结构与算法（12）—分治策略
2021-02-15 13:20
标签：list div 换问题 中间 ram 结构 int 就是 例子 分治策略是一种解决问题的思路： 将问题分为若干更小规模的部分 通过解决每一个小规模问题，并将结果汇总得到原问题的解。 PS：递归问题则体现了分治策略。 1.优化问题例子：找零兑换问题 让自动售货机每次找零给顾客最少数量硬币。 贪心策略解决：我们每次都试图解决问题尽量大的一部分对应到兑换硬币问题，就是每次一最多数量的最大面额值硬币来迅速减少找零面值。但这并不是最优解。虽然尽量保证了每次找的是最优的，但组合起来不一定是最优解，只是接近最优解。 可采用递归解法来解决：
代码： 数据结构与算法（12）—分治策略 标签：list div 换问题 中间 ram 结构 int 就是 例子 原文地址：https://www.cnblogs.com/yeshengCqupt/p/12714854.html
1 def recDC(coniValueList, change, knownResults):
2 ‘‘‘
3 :param coniValueList: 硬币面额数组
4 :param change: 需要找的钱
5 :param knownResults: 最优解的表
6 :return: 最优查找次数
7 ‘‘‘
8 minCoins = change
9 if change in coniValueList:#递归基本结束条件
10 knownResults[change] =1 #记录最优解
11 elif knownResults[change] >0:
12 return knownResults[change] #查表成功，直接用最优解
13 else:
14 for i in [c for c in coniValueList if c change]:
15 numConins = 1 + recDC(coniValueList,change - i,knownResults)
16
17 if numConins minCoins:
18 minCoins = numConins #最小的找零次数
19 #找到最优解，记录到表中
20 knownResults[change] = minCoins
21 return minCoins
22 memo = [0] *64 #记录中间结果的表
23 print(recDC([1,5,10,25],63,memo))
24 print(memo)