4.5找零问题的动态规划案例分析（Python进阶-数据结构与算法）课件

动态规划案例分析 数据结构与算法（Python版） item weight value 1 2 3 2 3 4 3 4 8 4 5 8 5 9 10 ❖ 大盗潜入博物馆 ， 面前有5件宝物 ， 分别 有重量和价值 ， 大盗的背包仅能负重20公 斤 ， 请问如何选择宝物 ， 总价值最高？ 数据结构与算法（Python版） 讨论：博物馆大盗问题 0 ❖ 我们把m(i, W)记为： 前i(1<=i<=5)个宝物中，组合不超过W (1<=W<=20) 重量， 得到的最大价值 m(i, W)应该是m(i-1, W)和m(i-1, W-Wi)+vi 两者最大值 我们从m(1, 1)开始计算到m(5, 20) 数据结构与算法（Python版） 讨论：博物馆大盗问题 0 m 0 1 2 3 4 5 ... 0 0 0 0 0 0 0 1 0 0 3 3 3 3 2 0 0 7 3 0 0 4 0 0 3 4 8 5 0 0 3 4 8 8 博物馆大盗问题：动态规划表格 数据结构与算法（Python版） 8 4 8 3 m(5,5)=m(4,5)=max(m(3,5), m(3,0)+8) w 0 8 i 4 4 3 数据结构与算法（Python版） 0 数据结构与算法（Python版） 0 ❖ 上面我们用动态规划和递归分别解决了博 物馆大盗问题 ❖ 由于递归算法简洁直观 ， 只要递归和记忆 化应用得当 ， 也能高效解决这类问题 ❖ 同学们可以把本案例与找零兑换问题的递 归和动态规划解法分别对比 ， 找出其中的 规律 数据结构与算法（Python版） 0 小结 ❖ 中间结果记录可以很好解决找零兑换问题 ❖ 实际上 ， 这种方法还不能称为动态规划 ， 而是叫做“ memoization（记忆化/函数 值缓存） ”的技术提高了递归解法的性能 数据结构与算法（Python版） 找零兑换：动态规划解法 0 ❖ 动态规划算法采用了一种更有条理的方式 来得到问题的解 ❖ 找零兑换的动态规划算法从最简单的 “ 1 分钱找零 ”的最优解开始 ， 逐步递加上去 , 直到我们需要的找零钱数 ❖ 在找零递加的过程中 ， 设法保持每一分钱 的递加都是最优解 ， 一直加到求解找零钱 数 ， 自然得到最优解 数据结构与算法（Python版） 找零兑换：动态规划解法 0 ❖ 递加的过程能保持最优解的关键是 ， 其依 赖于更少钱数最优解的简单计算 ， 而更少 钱数的最优解已经得到了。 ❖ 问题的最优解包含了更小规模子问题的最 优解 ， 这是一个最优化问题能够用动态规 划策略解决的必要条件。 originalamount找零兑换问题具体来说就是： 数据结构与算法（Python版） 找零兑换：动态规划解法 0 0 ❖ 采用动态规划来解决11分钱的兑换问题 从1分钱兑换开始，逐步建立一个兑换表 数据结构与算法（Python版） 找零兑换：动态规划算法 7 ❖ 计算11分钱的兑换法 ，我们做如下几步： 首先减去1分硬币，剩下10分钱查表最优解是1 然后减去5分硬币，剩下6分钱查表最优解是2 最后减去10分硬币， 剩下1分钱查表最优解是1 ❖ 通过上述最小值得到最优解： 2个硬币 1分 2分 3分 4分 5分 6分 7分 8分 9分 10分 0 数据结构与算法（Python版） 找零兑换：动态规划解法 数据结构与算法（Python版） 找零兑换：动态规划算法代码 循环结束，得到最优解 0 ❖ 我 们 注 意 到 动 态 规 划 算 法 的 dpMakeChange并不是递归函数 虽然这个问题是从递归算法开始解决，但最终我 们得到一个更有条理的高效非递归算法 ❖ 动态规划中最主要的思想是： 从最简单情况开始到达所需找零的循环 其每一步都依靠以前的最优解来得到本步骤的最 优解，直到得到答案。 数据结构与算法（Python版） 找零兑换：动态规划算法扩展 0 ❖ 前面的算法已经得到了最少硬币的数量， 但没有返回硬币如何组合 ❖ 扩展算法的思路很简单 ， 只需要在生成最 优解列表同时跟踪记录所选择的那个硬币 币值即可 ❖ 在得到最后的解后 ， 减去选择的硬币币值 , 回溯到表格之前的部分找零 ， 就能逐步 得到每一步所选择的硬币币值 数据结构与算法（Python版） 找零兑换：动态规划算法扩展 0 找零兑换：动态规划算法扩展代码 数据结构与算法（Python版） 0 找零兑换：动态规划算法扩展代码 数据结构与算法（Python版） 0 $$