找钱问题的动态规划解法

© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 计算机科学 塑 找钱问的动态规划解法 ‘ ’ 贾 驰 王相海 辽宁师范大学计算机与信息技术学院 大连 北京大学视觉与听觉信息处理 国家重点实验室 北京 摘 要 动 态规划算法对许 多实 际 问题是灵活和有效的 。 本文首先对一 类找钱 问题进行 了和讨论 , 然后 给 出 了该 问题的一种 动态规划解 法 , 最后 对所给算法 的复杂性进行 了分析 。 实脸结 果脸证 了所提 出算法的 有效性 。 关键词 动态规划 , 算法 , 找钱 问题 , 复杂性 一 , , , ‘ , 一 叮 , , · 比 , , , 引言 动态规划算法作为一种重要的算法策略为具有最优 子结构性质的实际 问题提供了一种重要 的解决 问题的途 径 该策略最早由 等人提出川 , 它利用最优性原理 和所获得的递推关系去求解最优决策序列 , 从而使问题的计 算量急剧下降 利用动态规划策略求解的问题通常可能会有 许多可行解 , 每一个解都对应于一个值 , 动态规划求解过程希 望获得具有最优值的那个解川 。几年来 , 人们在这一领域进行 了积极的研究 , 给出了很多具有重叠子问题特性问题的动态 规划解法 , 具体情况可参见文以 , 〕, 在现实生活的商品交易中经常涉及到找钱问题 , 如何设 计一个高效的找钱算法对于 自动控制 , 特别是经济领域机器 人的发展具有重要意义 。本文首先对找钱问题进行了说明 , 并 对该问题采用贪心策略所存在的问题进行了分析 , 进而对该 问题的最优子结构性质进行了证明 , 在此基础上给出了该问 题的递归结构 , 同时实现了其动态规划算法 。最后对所提出算 法的复杂度进行了分析和讨论 。 问题的提出 设有 二 种不同面值的硬币 , 各硬币的面值存于数组 〔 〕现要用这些面值的硬币来找钱 , 可以使用的各种面值的硬 币个数不限 问题 对于任意需要找的钱数 , 确定所使用的 最少硬币个数以及具体的找钱方案 。 找钱问题的贪心解法分析 对于找钱问题人们很容易想到贪心算法 , 比如假设有六 种面额分别为 。元 、 元 、 。元 、 元 、 元和 元的货币 , 现在要 找给某顾客 元钱 , 这时我们会不加思索地拿出一个 元 , 个 元 , 一个 元 , 一个 元和一个 元的货币交给顾客 , 此时采 用这种方法所拿出的货币个数是最少的 , 这种方法即为贪心 算法 贪心算法总是作出在当前看来是最好的选择 , 其特点简 单 , 因而人们 比较喜欢采用 但由于该策略不是从整体最优考 虑问题 , 因而它所做出的选择只是在某种意义上的局部最优 选择 比如在上面所举的例子中 , 如果所给的找钱面值改为 元 、 元和 元三种 , 而要找给顾客的是巧元钱 , 则按照上述贪 心算法 , 找给顾客的面额为 一个 元和四个 元钱 , 然而找三 个 元显然是最好的找法 贪心算法对诸如找钱等问题有时不 能得到整体最优解 找钱问题的动态规划解法 符号约定 设存于数组 司中的 个不同的面值呈递增顺 序 , 找出的钱数 满足 簇 , 示利用 种不同面值的硬 币找出钱数为 时所用的最少硬币个数 , 若找不 出钱数 , 则约定 , , 《 表示按照上述最优值 即 , 进 行找钱所需要的各硬币的个数 , 即 尸 , 表示当找钱数为 时 , 用到货币面值为 的硬币的个数 若 尸 , 。, 则表示没 用到面值为‘的硬币 问题的最优子结构性质 结论 对于任意需要找的钱数 , 一个利用 〔 司中的 , 个不同的面值货币进行找钱的最佳方案为 尸 , 力 , 尸 , , ⋯ , 尸 , , 即此 时的最 少硬 币个数 。 , 为买尸 , , , 则 尸 , , , 一尸 · , ,卜定是利用 , 本文受到国家自然基金项 目 。 、 辽宁省自然基金项 目 。。 、大连市科技基金项 目和辽宁省高等学校优秀人才支持计划 资助 。 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 〔 , 〕中的 刀 个不同的面值硬币对钱数 了 , 一 尸 , 〔 进行找钱的最佳方案 。 证明 假设 尸 , , ⋯ , 尸 , 不是最佳方案 , 不 妨假设 尸‘ , ,‘ , ⋯ , 尸 , , ‘ 利用 〔 二 〕中的 。 个 不同面值的硬币对钱数 了进行找钱的最佳方案 , 其 中 , 少 , , ⋯ , 表示新方案中对 找钱时所用到的 的个数 , 从而有 表示无穷大 」, , 利用 个面值为 〔 司的硬币 , 对钱数 进行 找钱 , 输出其最佳找钱方案和所需要的硬币个数 , 买尸 二 , , , 买 , ‘ ‘ , , , , , 进一步有 荟尸 , , 尸 二 , , 善尸 , ‘ , , 从而有 , , 买尸 , 二 汤 , , 产卜尸 二 , , 尸 , 二 , 色衣 ‘舞二里〔〕 〕 “ “ “ “ 团 〔〕口〕 〕 〕 “ ,, “ 〕 ” 〕〔〕 , , 买 , “ , , , , 》 〔 〕 一 一 且 “ , , , 夕, , 少, 艺尸 , 故 , , , 少‘ , ‘ , , ⋯ , ‘ , 了 也是利用 〔 司中的 , 个不同的面值货币对 进行 找钱的一个方案 , 并且其较方案 尸 , , 尸 , , ⋯ , , , 更加优秀 , 这与 , , , , ⋯ , 尸 , 为最佳方案矛盾 。 从而上述找钱问题具有最优子结构 性质 。 问题的递归结构 以下分几种情况讨论 当 二 一 时 , 即只能用一种硬币找钱 , 硬币的面值为 〔〕, 此时有 一 〔一 〔〕 一 一 十 十 而 口一 一 〕〕 一 一 〕〕 一 一 〔一 〕 一 〔〕一 ” 一 ” “ “ 加 一 一 〕 二 〔〕 〕 〔〕〔〕于 旦 场 」 」一 」十 即 , 阳 〕一 ” 〕 〕 , 〔〕, 〔〕 农各 二」 找不开 叮、,汀、、,叮、 , 当 〔 〕, , 〔 。 〔〕异 。 吕衣少 〔」 。 其余 时 , “ 一 ” 二 〔」〔 ” 巨 ①若 少 ’仁司 , 即用 ”种硬币找钱 , 且第 种硬币面值 与找的钱数 少相等 , 此时有 。 , 少 , 丁 〕 ‘ , 尸 , 丁 〕 , ￡一 「〕 , 共 〕 ② 若 〔。 〕, 即第 , 种硬币面值比所找钱数大 , 故找 钱所使用的硬币只需考虑 一 〕即可 , 故此时有 , 一 , 【 〕, 夕 。 ③若 少 〔司 , 即第 。 种硬币面值比所找的钱数少 , 故 种硬币都可以用来找钱 , 此时有 , 砂 , 一 〕 ‘ 盛‘ 若当 五为 花。 簇 簇的时 , 。 , 力达到最小值 , 则有 尸 , 。 〕, 一尸 〔尤。 , 一 队。 〕 算法的实现 设数组 〔 司中存放的是 。 个呈递增顺序的不同面值 , 所要找的钱数 满足 簇 , 其中 是由用户输入的 数组 口〕表示利用 〔 司找钱数为 时所用的最少硬币个数 , 即 最优值 尸【」〔月 , 《 表示按照上述最优值找 钱 时用到货币面值为 的硬币的个数 , 即最优解 。 按照上述 递归公式所给出的递推算法如下 一 「」二 」 ”城一 “ “ ” 团 〔〕〔 〔〕 , 〕 “ 仁〕口〕 一 〔〕 “ ,, 开 “ 〕〔 〔 〕 的 〔〕 〕 ” ” “ “ 〔 〕口〕 〔〕、 ,, “ 」口」 算法的实验结果 我们利用如下主调函数对所设计的算法进行了实验 。 , , 〔 〕 即场 , ” 即 〔 ” “ 〕“ 十 」 , , © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 运行结果如下 , 〔 〕 〔 一 〔 二 〔〕一 。 一 〕一 〔 〕 〕 〕 一 〔〕 〔 〔〕 〔〕 〔〕 〔 习 〔〕 〕 〔〕一 〕 〕 〕 〔〕 〔 〕 〔〕 〔〕一 。 〔〕 〔〕 〕 〕 〔〕 〔〕 〔〕 〔〕 〔〕 〕 〔〕 〕“ 〔习 〔〕一 〔〕一 。 〔〕一 〕 〔〕 〕 〔〕 〔 一 〔〕 〕 〕 〔〕 〔〕 〕 〔 〕 〔〕一 〔〕 〔〕 〕 〕二 〕 〔 〔〕 〔〕 一 〕一 〔 〔〕 〔 〕 〕 〔〕 〔〕 〔〕 〕 〕 〔〕 〔 〔 〔〕一 。 〔 一 〔 〔 仁〕 〕 一 〕 〔〕 〔 仁〕一 〔」 〔〕 〔〕 〔〕 〔〕 〔〕 算法复杂性分析 时间复杂性 由前面算法可知 , 在计算最优值 时 , 有两次循环 少 和 乙衣 一 , 若每次都 执行循环体里面的 ￡ ‘ , 即算法的最坏时 间复杂度为 矛 若不执行循环体里面的 , 即算法的最好时 ’复杂度为 只 , 。 在计算最优解 尸 , 时 , 由于打印出来的是一二维数 组 , 所以多了一层循环 , 因而最好情况下的时间复杂度为 矛 , 而最坏情况下的时间复杂度为 ” 空间复杂性 过程 。 中 , 计算 力时使用了一个长度为 的数组和 若干个简单变量作为临时存储单元 , 故空间复杂性为 , 即为 。 同理计算 , 夕 时 , 用了一个二维数组 尸 〔〕和如果简单变量作为临时存储单元 , 故此时的空间 复杂度是 动 。 结束语 本文通过理论上的分析 , 说明了贪心算法在解 决找钱问题上的不足 , 并进一步证明了该问题可用动态规划 求解的最优子结构性质 , 在此基础上给出了问题最优值和最 优解的递归关系以及问题求解的具体算法 , 最后对算法的时 间和空间复杂性进行了分析和讨论 , 算法的复杂度是比较令 人满意的 。 实验结果验证了方法的有效性 。 参 考 文 献 而 · 记 闪 , 余祥宣 , 崔国华 , 邹海明 计算机算法基础 武汉 华中科技大学出 版社 , 主 , 一 · · 夕 王晓东 计算机算法设计与分析 北京 电子工业出版社 , 。。 上接第 页 由于这里能够系统地进行设计 , 就必须重点考虑以下几 个问题 在资源库中建立跨学科的知识描述机制 基于传统的 资源库 , 常见的协作学习只是对应于某一领域知识的协作学 习 , 系统的知识框架也是针对某一特定学科的 这就大量失去 参加学习的角色 教师 、学习者 、泛化的角色 的个性 , 使协作 流于形式化 、 作品化 。 其主要原因之一 , 是由于系统在设计时 没有一个跨学科的知识描述机制 教育资源 。 数据库 一一一一卜 翔 文档 教育资源 一 文档 二二李领域数据库 一服务平台一客户端教育资源 一 文档 一资源信息标准化 教教育资源 。 数据库 一一一一卜 翔 文档档 教教育资源 一 文档 二二李领域数据库 一服务平台一客户端端教教育资源 一 文档 一一资资源信息标准化化 图 建立协同对象互操作语义视图 。 为了使协作学习具有 个性化 、避免形式化和作品化 , 还应在协同学习环境里 , 建立 协同对象互操作语义视图 。这是因为协作学习的角色可能分 布在不同地方甚至是不同国家 , 他们所用的物理环境也可能 是异构的 因此 , 这些对象之间就存在着语义差别 , 使得对象 之间的互操作变得困难 。 目前的研究大都是对多信息源采用 统一的对象描述及视图来处理协作对象的互操作问题 。 在此 基础上 , 建立互操作语义视图 , 可能是效率更高的思路 。 建立可以基于协同学习 目标而进行资源重组的资源重 组机制 这是有效利用现有资源 、使协同学习真正实用的主要 途径 , 也是建立跨学科的知识描述机制和建立协同对象互操 作语义视图的目的 结束语 以上讨论了基于资源的计算机支持的协作式学 习 的描述 、 结构和实现思路 , 并简要介绍了我们的 部分工作 。 是一种新的探索 , 特别是资源重组和寻求 合适的 模式更是今后必须面对的挑战 。 有关文献 已经 从 “ 网格 ” 、 “ 主体 ” 、“ 本体 ”、 “ 对等网 ” ⋯ ⋯和学习理论等方面 开展研究 , 这将有力推动 的研究和实际应用 。 参 考 文 献 李吉桂 李小文 , 邹家炜 计算机支持的协同学习 系统的结 构 、工作模式和开发策略 计算机科学 , , 网格环境中资源发现机制的研究 。 即 网络异步一学习管理系统 · 刀 · 一 卜 动 王桂玲 系统和工具的分类与比较 刀 。 黄荣怀 · 的理论与方法 北京师范大学 ·