论文研究 兑换零钱问题的动态规划算法研究.pdf

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