兑换零钱问题的动态规划算法研究

• 作者: 严华云
• 来源期刊: 计算机应用研究
• 关键词: 动态规划 兑换零钱问题 算法复杂性
• 年，卷（期）: 2007,（12）
• 所属期刊栏目: 研究探讨
• 页码范围: 88-90,93
• 页数: 4页
• 分类号: TP311.11
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2007.12.026

摘要

兑换零钱问题是一个求解组合优化的问题.首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的动态规划算法的O(Mn2)提高到本算法的O(n3),空间复杂性由通常的动态规划算法的O(Mn)提高到本算法的O(n2),因此效率有了较大提高.最后通过实验对算法进行验证,证明了算法的高效性.该算法可以广泛应用于自动售货机.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	严华云	湖州师范学院信息工程学院	18	82	3.0	8.0