%0 Journal Article
%T Research on money change problem through dynamic programming<br>兑换零钱问题的动态规划算法研究*
%A YAN Hua-yun
%A <br>严华云
%J 计算机应用研究
%D 2007
%I 
%X 兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的动态规划算法的O（Mn2）提高到本算法的O（n3）,空间复杂性由通常的动态规划算法的O（Mn）提高到本算法的O（n2）,因此效率有了较大提高。最后通过实验对算法进行验证,证明了算法的高效性。该算法可以广泛应用于自动售货机。
%K dynamic programming
%K money change problem
%K complexity algorithm<br>动态规划
%K 兑换零钱问题
%K 算法复杂性
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=A9D9BE08CDC44144BE8B5685705D3AED&aid=4ED612C44F3F491A84902650E424CE44&yid=A732AF04DDA03BB3&vid=B91E8C6D6FE990DB&iid=59906B3B2830C2C5&sid=7E8E8B150580E4AB&eid=869807E2D7BED9EC&journal_id=1001-3695&journal_name=计算机应用研究&referenced_num=0&reference_num=10