| 兑换零钱问题的动态规划算法研究 |
| |
| 引用本文： | 严华云.兑换零钱问题的动态规划算法研究[J].计算机应用研究,2007,24(12):88-90. |
| |
| 作者姓名： | 严华云 |
| |
| 作者单位： | 湖州师范学院,信息工程学院,浙江,湖州,313000;同济大学,电子与信息工程学院,上海,201804 |
| |
| 基金项目： | 国家自然科学基金资助项目（60573056）；浙江省自然科学基金资助项目（Z106335，Y105090）；湖州市科技计划资助项目（2006GG03，2006YG01，2007YZ08） |
| |
| 摘 要： | 兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的动态规划算法的O（Mn2）提高到本算法的O（n3）,空间复杂性由通常的动态规划算法的O（Mn）提高到本算法的O（n2）,因此效率有了较大提高。最后通过实验对算法进行验证,证明了算法的高效性。该算法可以广泛应用于自动售货机。
|
| 关 键 词： | 动态规划 兑换零钱问题 算法复杂性 |
| 文章编号： | 1001-3695(2007)12-0088-03 |
| 修稿时间： | 2006年11月12 |
Research on money change problem through dynamic programming |
| |
| YAN Hua yun.Research on money change problem through dynamic programming[J].Application Research of Computers,2007,24(12):88-90. |
| |
| Authors: | YAN Hua yun |
| |
| Affiliation: | (1.School of Information & Engineering, Huzhou Teachers College , Huzhou Zhejiang 313000, China; 2.College of Electronics & Information Engineering, Tongji University, Shanghai 201804, China) |
| |
| Abstract: | Money change problem is a combinatorial optimization problems. Firstly, analyzed money change problem, and prpoposed a dynamic programming algorithm. Then, analyzed the space complexity and time complexity of the algorithm, enhanced the space complexity from O(Mn2) of general algorithm to O(n3) of this algorithm, enhanced the time complexity from O(Mn) of general algorithm to O(n2) of this algorithm, thus improved the efficiency much. Finally tested the algorithm through simulation, and found the algorithm was high efficient. This algorithm can be used in the field of automatic sales. |
| |
| Keywords: | dynamic programming money change problem complexity algorithm |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
|
