文件名称：论文研究-兑换零钱问题的动态规划算法研究.pdf
文件大小：160KB
文件格式：PDF
更新时间：2022-08-11 13:31:15
动态规划,兑换零钱问题,算法复杂性
兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析，证明了该问题满足动态规划的最优化原理，并给出了其动态规划解法；然后对本算法进行了时间复杂性和空间复杂性分析，得到时间复杂性由通常的动态规划算法的O(Mn2)提高到本算法的O(n3)，空间复杂性由通常的动态规划算法的O(Mn)提高到本算法的O(n2)，因此效率有了较大提高。最后通过实验对算法进行验证，证明了算法的高效性。该算法可以广泛应用于自动售货机。