兑换零钱问题的转换求解方法  

A Solution of Money-changing Problem by Transformation

作　　者：张伟志[1] ZHANG Weizhi(Department of Computer and cyberspace security,Fujian Normal University,Fuzhou,China,350000)

机构地区：[1]福建师范大学计算机与网络空间安全学院,福州350000

出　　处：《福建电脑》2023年第8期42-45,共4页Journal of Fujian Computer

基　　金：福建省自然科学基金(No.2022J01398)资助。

摘　　要：兑换零钱问题是计算机科学中的一个经典问题。它在自动售货机、生物化学等方面都有着广泛的应用。传统的动态规划算法求解兑换零钱问题的时间和空间复杂度都比较高,与需兑换零钱的金额相关。本文通过将兑换零钱问题转换为一系列子问题的方法,将兑换零钱问题的时间和空间复杂度都大幅降低。最后,本文通过理论和实验验证了算法的高效性。The money-changing problem is a classic problem in computer science.It is widely used in vending machines,biochemistry,and other fields.The time complexity and space complexity of the traditional dynamic programming algorithm for solving the money-changing problem is relatively high,and it is related to the amount of money to be exchanged.By converting the problem of exchanging coins into a series of subproblems,the time and space complexity of the problem is moderately reduced.Finally,we verifies the efficiency of the algorithm through theory and experiments.

关 键 词：动态规划 兑换零钱 问题转换 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]