兑换零钱问题的动态规划算法研究

维普资讯 http://www.wendangwang.com

第2 4卷第 l 2期 20 0 7年 1 2月

计算机应用研究 Ap l a in Re e r h o mp tr p i t s a c fCo u e s c o

Vo . 4 No 1 12 . 2 De . 2 0 c o7

兑换零钱问题的动态规划算法研究米 严华云 ( .州师范学院信息S程学院, 1湖 -浙江湖州 330; . 100 2同济大学电子与信息工程学院,上海 2 1 4 08 ) 0 摘要:兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,明了该问题满足动态证

规划的最优化原理,给出了其动态规划解法;并然后对本算法进行了时间复杂性和空间复杂性分析,到时间复得

杂性由通常的动态规划算法的 D M 提高到本算法的 D n)空间复杂性由通常的动态规划算法的 D M ) ( n) (, ( n提高到本算法的 D n)因此效率有了较大提高。最后通过实验对算法进行验证,明了算法的高效性。该算法 (,证 可以广泛应用于自动售货机。

关键词:动态规划;兑换零钱问题;算法复杂性中图分类号:T 3 1 1 P 1. 1文献标志码:A 文章编号:10—6 5 20 ) 2 0 8— 3 0 13 9 ( 0 7 1—0 8 0

Re e r h o n y c a g r b e t r u h d n mi r g a s a c n mo e h n e p o l m h o g y a c p o r mmi g n YAN Hua y n '— u

(. col厂 n rai 1Sho I om tn& E gneig HuhuTahr Clg HuhuZ ea g3 30 C ia 2 Clg l t nc& I om tn D f o n i r, zo ece o ee, zo h in 100, hn; . o eeD e r i e n s l j l,E c o s n r ai f o

E gnei n i r g,Tn nvrt, h n h i 0 84,C ia e n ogiU i sy S ag a 2 10 ei hn ) Ab t a t Mo e h n e p o l m o i ao il p i z t n p o l ms i t sr c: n y c a g r b e i a c mb n tr t s a o mi i r b e .F r l ao s y,a ay e n y c a g r b e n lz d mo e h n e p o l

m,a d p - n r p p s d a d n mi r gammig ag rt m、 Th n,an lz d t e s a e c mp e iy a d tme c m pe iy o h l oihm, e— o oe y a cpo r n lo ih e ay e h p c o l xt n i o lxt ft e ag rt n

h n e esa e o pe i o Mn )o n rl lo tm t 0 n )o ti a o tm, n a c dte i e o pe i o a cd t c m l t f m 0( f e ea a r h ( f hs l r h e h n e m m l t f m h p c xyr g gi o gi h t c xy r 0( )o ee l grh o0( fti a o t Mn fgnr o tm t aa i l n )o s l rh h gi m,tu m rvdteeii c uh i l etdtea o t h si poe lee ym c .Fn l t e h l rh h t n ay s gi m t r u h s l t n n o n h lo tm sh g— f ce t hs ag r h c n b s d i h ed o u o t ae . h o g i ai,a d fu d t e ag r h wa ih ef i n .T i lo t m a e u e n te f l f t mai sl s mu o i i i i a c Ke y wor ds: d n mi r ga mig;mo e h ng rblm;c mp e iy a g rtm y a c porm n n yc a e po e o l xt lo ih

动态规划是求解决策过程的有效最优数学方法之一。。 它为具有最优子结构性质的实际问题提供了一种重要的解决 问题的途径 J。该策略最早由 B l a出, e m n提。它利用最优 l性原理和所获得的递推关系去解最优决策序列,而使问题的从计算量急剧下降。利用动态规划策略求解的问题通常可能会

1士; 2便同样,以前法国的币制也存在这样的问题。因此本文对该问题用动态规划算法加以解决,以避免非十进制换算的币制体系不能用贪心算法解决。其间证明了兑换零钱问题可以进行动态规划,出了该问题的最优子结构性质的证给 明以及该问题的递归结构 (叠子问题 )同时用 C+重;+实现

有许多可行解

,每个解均对应一个值,动态规划求解过程希望获得具有最优值的那个解。多年来,们在这一领域进行人了积极的研究,给出了很多具有重叠子问题特定问题的动态规 划解法。详细情况可参见文献[,] 89。

了其动态规划算法。最后对该算法的复杂度进行了分析。

1兑换零钱问题的贪心解法 1 1兑换零钱问题的问题表述、 一

兑换零钱问题有其广泛的应用前景,如应用到自动售货 机上进行零钱兑换。被称为“不下班的超级营业员”的自永 动售货机在中国特别是发达国家越来越普及,目前自动售但

个货币系统有 n种不同面值的钱币,种钱币的面值分各

别为,,,。其中 T=1 …,。要怎样兑换价值为的钱 (即面值为的兑换零钱问题 )使钱币的数目最少。形式地, n

货机出售商品时,机器只能接收硬币和小额纸币,响到消影费者的选择。如何解决该问题,中关键的技术包括对大其额纸币的零钱兑换问题。由于运行在自动售货机上,设计一个高效的兑换零钱算法对于本问题相当重要。本文首先分

说,让量。约束条件要在 …

T:M下极小。其中:,,

,

是非负整数,示该种币值 ( i的个数;表 T)如果其中=

析了用贪心算法解决该问题。由于贪心算法固有的缺点决定了其并不总能解决最优问题,还需要进行证明其算法的 最优性。比如说世界上通行的货币体制为十进制,这种货币

0,则指没有该种币值 ( i。 T) 1 2兑换零钱问题的贪心解法分析 .对于兑换零钱问题的贪心算法可以这样实现: 假设 T<<…<, l

体制的零钱兑换问题用贪心算法兑换可以证明是最优的。 但有少数的币制不是十进制的就未必能用贪心算法兑换,如对于以前的英国货币单位是 1镑等于 2令,英 0先 1先令等于 收稿日期: 06 1 -2 2 0 - 1 1;修返日期:20—0 1 07 1—8

输入:需要兑换零钱的数,,, T;。 …,n

输出:根据 X i的值输出的个数。[]

基金项目:国家自然科学基金资助项目(0 7 0 6;江省自然科学基金资助项目 65 3 5 )浙

(163, 159 )湖州市科技计划资助项目(06 G 320Y

0, 0 Y 0 ) Z035Y 000; 20 G 0, 6 G 12 7 Z8 0 0 作者简介:严华云( 9 2 )男, 17。,讲师,博士研究生,主要研究方向为信息检索、数据挖掘、息安全、信计算机辅助设计( ah@h t z c ) yn y uc j n . . .

http://www.wendangwang.com

你可能喜欢

  • 问题报告
  • c语言资料
  • 算法设计与分析答案
  • 算法设计与分析王晓东
  • 算法合集
  • 动态规划经典
  • 动态规划问题
  • ppt2010

兑换零钱问题的动态规划算法研究相关文档

最新文档

返回顶部