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

第 39 卷 第 8 期 福 建 电 脑 Vol.39 No.8 2023 年 8 月 Journal of Fujian Computer Aug.2023 本文得到福建省自然科学基金（No.2022J01398）资助。张伟志（通信作者），男，1999年生，主要研究领域为人工智能、数据挖掘。E-mail:。兑换零钱问题的转换求解方法 张伟志(福建师范大学计算机与网络空间安全学院 福州 350000)摘 要 兑换零钱问题是计算机科学中的一个经典问题。它在自动售货机、生物化学等方面都有着广泛的应用。传统的动态规划算法求解兑换零钱问题的时间和空间复杂度都比较高，与需兑换零钱的金额相关。本文通过将兑换零钱问题转换为一系列子问题的方法，将兑换零钱问题的时间和空间复杂度都大幅降低。最后，本文通过理论和实验验证了算法的高效性。关键词 动态规划；兑换零钱；问题转换 中图法分类号 TP301.6 DOI:10.16707/ki.fjpc.2023.08.009 A Solution of Money-changing Problem by Transformation ZHANG Weizhi(Department of Computer and cyberspace security,Fujian Normal University,Fuzhou,China,350000)Abstract 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.Keywords Dynamic Programming;Money-changing Problem;Problem Transformation 1 引言 在兑换零钱问题中，需要用 k 枚面值不同的硬币兑换价值为 n 的金额，求得所需最小的硬币数，且1 2 (1,)时一定有解7。目前，关于如何求解 Frobenius 数，Wilf 提出了时间复杂度为(1)的“circle-of-light”算法8，Nijenhuis 提出了时间复杂度为(11)的算法9。针对一个具体的零钱 n 分解问题，传统的动态规划算法在()的时间复杂度下，得到最少硬币数的最优解10。S Bocker 等人提出了一个时间复杂度为(1)的算法来求得零钱 n 的一个解，但不一定是最优解2。本文将一个兑换零钱 n 的原问题转换为一系列硬币为=1，兑换的零钱金额 21的子问题。通过动态规划求解子问题，子问题的运行结果可以重复利用。本文提出了一个时间复杂度为(min，2)，空间复杂度为2023 年 福 建 电 脑 43(min，k1)，求解最少硬币数的算法。2 方法介绍 2.1 算法思路 对于给定 k 枚面值不同的硬币1,，兑换 n零钱的问题。令=，=/，使得=+。定义：=1,1 2 =1 (1),0 (1)对于每个可以理解为：零钱 n 兑换 枚后，还需要兑换金额+1+(1)。此时，若再兑换+枚1，则多兑换。因此需要把部分1硬币换成1,2，从而将多兑换的部分减去。即在=12=，满足=12+。最后只需依次计算01,1，02,2，0,，能否在=12=，满足=12+。若满足，则停止计算，返回最优解为+。当遍历所有情况，仍无解时，该问题无解。2.2 算法证明 2.2.1 充分性证明 若 1,2可 以 在=12=，满 足=12 +，则存在一个硬币数为+的解。证明如下：=12=12+(=12+)1=12+(=12+)1+()=存在一个硬币数为+的解。证毕。2.2.2 必要性证明 反之，若存在一个+的解，设硬币的使用个数为 ，0 ，0 ，则=12=，=12 +。证明如下：=11=+()=+=12=11=+=1=+硬币的使用个数为 =12+(+()=12)1+()=+=12+(=12+)1=12=，=12 +。证毕。2.2.3 结论 综上，通过本文的方法，一个兑换零钱 n 的原问题可以转换为一系列硬币为=1，兑换的零钱金额为的子问题。2.3 算法举例 以 n=395、硬币组88，296，346，368，423为例进行说明。此时 r=395，q=0，=280，72，22。当计算到05时，(+)1。可得，当i=0，j5 时，(+)1，故不存在=12+时，满足=12=。故 n=395 时无解，如表 1 所示。表1 兑换零钱为 395 的 j=2 j=3 j=4 j=5 i=0 341 709 1077 1445 以 n=1241、硬币组88，296，346，368，423为例进行说明。此时 r=395，q=2，=280，72，22。依次计算02、12、22、03。都不存在=12 +时，满足=12=。当13=654时，21+2+3=654。故 n=1241 的最优解为+=5，如表 2 所示。表2 兑换零钱为 1241 的 j=2 j=3 j=4 i=0 341 709 i=1 286 654 i=2 231 2.4 引入字典 为了防止重复获取用兑换的解=12，定义字典 d。每次计算一组0,的解时，更新字典 d。对于每列 j，更新字典，使得：(1)/(1)=0(的解+/(1)，0/(1)(2)假设=3，1=10，00=29，10=19，20=9。00、10、20的解分别为 4、4、无 解。更 新d92=4+2，2=6，2，d91=min(4+2，4+1)，2=5，2，d90=min(4+2，4+1，无穷大+0)，2=5，2。假设01=44 张伟志：兑换零钱问题的转换求解方法 第 8 期 49，11=39，21=29，31=19，41=9。根据1=19，查字典 d91=5，2，表示31=9+1 10，21=9+2 10，这2个数的=12 最小值为(d910 19/10)=0。验证：31时=12 的值为 4-3-1=0，21时=12 的值为 4-2-1=1。而 d92+1不在字典 d 中，所 以 01=49，11=39，需 要 计 算 对 应 解=12，并且更新字典 d。2.5 算法实现 算法的伪代码如下。其中，imin 表示计算到时 i 的最小取值，使得(+)1。ans=dp(bij,a)通过传统的动态规划求解。通过保存计算结果，在求解更大的bij时，可以利用已经求解的值。算法 兑换零钱 输入 需要兑换的零钱 n，硬币数组1,输出 所需最少硬币数，无解返回-1 def money_change(n,a):if(k=1)return 直接计算解;计算 q，r，;imin=0;for(j=0;j n/1+1;j+)查询,在字典 d 中的部分，判断是否有解。若有解，return j+q;遍历,不在字典 d 的部分 if(+)1)imin+=1;Continue;/*if(1 (+)1)*/ans=dp(,)#使用传统动态规划计算 if(ans=i+j)return j+q;更新字典 d;/*遍历,*/*for(j=0;j(+)1时 continue，所以max_(+)1，化简得 r+(1)1。当 1时，i 1=1，2。max_=1 (1)21。此时(max_)=(1)。当 1时，因 为(1,)(11)(1)9，所以 (1,)+。对于(1,)+1，(1,)+，由 Frobenius数的性质，必有解，所以+(1,)+1，。(1,)+，都有 0，(1,)+1，(1,)+，所 以 ，max_=1 (1)1，(max_)=(1)。综上，算法中动态规划算法 dp(,)的时间复杂度为(1)，空间复杂度为(k1)。由于字典 d 的存在，算法中 ans=dp(,)语句的调用次数 max_ 21。字典的查询次数 (0+)/2 22。因此这部分时间复杂度小于(2)。因此，结合上述两部分的复杂度，本文提出的方 法 时 间 复 杂 度 为(2)，空 间 复 杂 度 为(k1)。考虑到在 2/(为某一常数)时，使用传统动态规划算法进行求解，在2/时，使用本文提供的方法。此时，算法的时间复杂度为(min，2)，空间复杂度为(min，k1)。3.2 实验结果 实验使用 0，10000，1,为1，88，125，148，204，296，305，346，368，423，对照组为常规的动态规划算法，图像的横坐标表示当前的问题规模，纵坐标表示 0，平均计算时间。经过多次实验，若使用其他参数，和1,也有类似结果。实验结果如图 1 所示。可以观察到，在取值较小的时候，本文的算法运行时间较长。是随着取值不断增大，本文的算法运行时间平稳趋向一个定值，而传统的动态规划算法运行时间线性增长。2023 年 福 建 电 脑 45 图1 本文方法和动态规划运行时间比较 4 结束语 本文将一个兑换零钱问题转换为一系列硬币为=1、21的问题，然后通过传统的动态规划算法进行求解。这样就可以将问题规模 n 缩小到1。本文通过理论验证算法的时间复杂度为(min，2)，空间复杂度为(min，k1)。最后，本文通过实验和理论验证了算法的高效性。参 考 文 献 1 S Bcker,Z Liptk.The money changing problem revisited:Computing the frobenius number in time O(k a1)/Computing&Combinatorics,International Conference,Cocoon,Kunming,China,2005 2 Bocker S,Liptk Z.A fast and simple algorithm for the Money Changing Problem.Algorithmica,2007,48(4):413-432 3 Ramrez-Alfonsn,J.L.The Diophantine Frobenius Problem.Oxford:Oxford University Press,2005 4 Aardal,K.,Hurkens,C.,Lenstra,A.K.Solving a system of diophantine equations with lower and upper bounds on the variables.Math.Operations Research,2000(25):427-442 5 Aardal,K.,Lenstra,A.K.Hard Equality Constrained Integer Knapsacks.Informs,2004(29):738-738 6 Davison,J.L.On the linear diophantine problem of Frobenius.J.Number Theory,1994,48(3):353-363 7 Bcker S,Liptk Z,Martin M,et al.DECOMPfrom interpreting mass spectrometry peaks to solving the Money Changing Problem.Bioinformatics,2008,24(4):591-593 8 Wilf H S.A circle-of-lights algorithm for the“money-changing problem”.The American Mathematical Monthly,1978,85(7):562-565 9 Nijenhuis A.A minimal-path algorithm for the“money changing problem”.The American Mathematical Monthly,1979,86(10):832-835 10 S.Martello,P.Toth.Knapsack Problems.Chichester:Wiley,1990