问题是这样的:某个国家一共发行了a1,a2,a3,...,ak种不同面值的钞票,为了方便起见,假设a1,a2,a3,...ak依次增大。现在手上有的钱数为n,请问要如何把兑换成a1,a2,a3,...,ak这些钞票,使得所用的钞票的量为最少。这个问题看上去很简单,举一个例子,如果有1元,5元,10元3种钞票,而要兑换107元,于是就有a1=1,a2=5,a3=10,n=107。那么我们用面额最大的去除,那就是最大面额钞票的张数,比如说n/a3=107/10=10,亦即10元的10张;除过之后就有余数7,再用次大面额钞票去除,7/5=1,余数为2,所以5元钞票为1张;再把余数用第三大的面额去除,2/1=2,余数为0,于是一元的2张,没有剩下的钞票了,因此结果就是10元的7张,5元的1张,1元的2张。不过对有1元,5元,10元这个例子倒是正确,那么如果面额换为1元,3元,4元,要兑换10元的钞票呢?用上面的方法算一下,就是4元的2张,1元的2张,一共用了4张的钞票。但是若用2张3元的,1张4元的也能兑换出10元的,但却只用了3张钞票。所以看来平常的方法并不能解决“使所用钞票的量为最少”这个问题
这个问题有很多的解法,这里只想介绍利用动态规划(Dynamic Programming)和回溯的技巧来解决。
首先说说用到的数据结构,假设n是要兑换的钱数,k是能够提供的面额数目,如果要兑换100元,提供面额为1元,5元,7元的3种钞票于是有n=100,k=3。用一个数组base[]把面额先保存好,因此就有base[0]=1,base[1]=5,base[2]=7。但是这里我们假设一定提供面额为一元的钞票,否则可能有一些值兑换不出来。我们再用一个数组money[]存放兑换的钞票数,因此money[i]就是i元钱兑换出来的钞票数,由于money[0]表示0元兑换出来的钞票数,那么很自然就是0了,money[1]按照上面的假设一定是1。
其次我们说说具体的算法,假设现在要兑换i元,先看i-base[0],i-base[1],... ,i-base[k-1]是什么。例如:i=10,而面额是{1,3,4},于是这几个值就是10-1=9,10-3=7,10-4=6,换句话说,如果已经兑换好了9元7元或6元的话,要兑换十元只不过是加一张钞票而已。因此,在i-base[j]的情况下,就是多一张j元。但是,如何知道兑换i-base [j]要多少张钞票呢?别忘了money[]啊,该钞票的张数就在money[i-base[j]]中。如果已经已经兑换出i-base[j]元,用了money[i-base[j]]张钞票,于是再多加一张base[j]元就可以兑换出i元了,这样兑换i元一共用了money[i-base[j]]+1张钞票。
但是我们还没有解决题目所要求的钞票张数最少的问题,所以我们就要求出各个money[i-base[j]]+1的极小值来(j=1,2,...,k),再存在money[i]中,于是money[i]就是兑换i元的最少钞票张数了。要注意:因为i-base[j]一定小于i,所以在计算money[i]时,在i之前的值就一定要先算出来,这样money[i-base[j]]才会一个有意义的值。
说了很多,下面看看一个具体的规划的表格,还是以n=10,base[]={1,3,4}为例:
i money[i] i-base[j]
------------------------------------------------------------
0 0 --, -- , --
1 1 --, -- , --
2 2 2-1, 2-3*, 2-4*
3 1 3-1, 3-3 , 2-4*
4 1 4-1, 4-3 , 4-4
5 2 5-1, 5-3 , 5-4
6 2 6-1, 6-3 , 6-4
7 2 7-1, 7-3 , 7-4
8 2 8-1, 8-3 , 8-4
9 3 9-1, 9-3 , 9-4
10 3 10-1,10-3 ,10-4
-------------------------------------------------------------
*表示小于零,不用理会极小值,只要根据表格进行回溯就能得出结果了,看表格发现用10-3和10-4进行回溯的结果是一样的,也就是3+3+4=10和4+4+3=10的道理了,C语言的代码如下:
- #include <stdio.h></stdio.h>
- #include <stdlib.h></stdlib.h>
- #define MAXSIZE 100
- #define min(a,b) ((a) <= (b) ? (a) : (b))
-
- int main(void) {
- int money[MAXSIZE+1];
- int base[] = { 1, 3, 4 };
- int k = sizeof(base)/sizeof(int);
- int n;
- int i, j, MIN;
- char line[100];
- printf("\nMinimum Money Change Program");
- printf("\n----------------------------");
- printf("\n\nBase Values : ");
- for (i = 0; i < k; i++)
- printf("%d ", base[i]);
- printf("\n\nYour input please --> ");
- gets(line);
- n = atoi(line);
- money[0] = 0;
- money[1] = 1;
- for (i = 2; i <= n; i++) {
- MIN = n;
- for (j = 0; j < k; j++)
- if (i >= base[j])
- MIN = min(money[i-base[j]]+1, MIN);
- money[i] = MIN;
- }
- printf("\n\nMinimum = %d", money[n]);
- getchar();
- }
当然这个程序还有一个不足,那就是没有将每个面额的钞票的张数输出,还需要对程序进行一些改进,有兴趣一起研究一下吧...
分享到:
相关推荐
2. **求解过程**:采用递归的方式,利用动态规划的思想来解决问题。动态规划是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。 3. **输出结果**:将计算出的方案总数写入文件`output.txt`。 ...
动态规划在硬币兑换问题中的应用,不仅为我们提供了一个高效的解决方案,还向我们展示了算法在处理实际问题时的强大能力。通过这种方式,我们可以将看似复杂的问题拆解为简单的子问题,再利用递推关系将子问题串连...
特别是在动态规划问题中,通过利用单调性可以有效地优化算法的时间复杂度,使得原本不可行的问题变得可解。本文通过几个具体的例子,探讨了如何在动态规划中应用单调性,并通过具体的题目来加深理解。 #### 序言 在...
9. **伪代码和实例**:压缩包内的内容可能包含了一些动态规划问题的伪代码和具体实例,比如零钱兑换问题、最长递增子序列、矩阵链乘法等,帮助读者理解动态规划的实施步骤。 10. **解题技巧**:学习动态规划,除了...
### 动态规划(Dynamic Programming)详解:算法优化之道 #### 引言 ...在实际应用中,灵活运用动态规划的解题步骤,结合具体问题的特点,将有助于提高算法设计的能力,并在解决实际问题时更加得心应手。
这些资源可以帮助用户更好地理解和解决 LeetCode 上的动态规划问题。 从压缩包子文件的文件名称 "组合" 来看,我们可以推测其中可能包含与组合相关的动态规划题目。组合问题往往涉及到从一组元素中选择特定数量的...
通过C++的编程实现,我们可以利用其强大的面向对象特性,构建出高效、灵活且易于维护的解决方案。对于学习金融信息系统或者C++编程的学生来说,这样的项目不仅能够提升编程技能,还能增进对金融市场的理解。
良好的用户体验离不开对各种异常情况的妥善处理,如网络中断、积分不足等,源码应提供明确的错误提示,帮助用户解决问题。 8. **权限控制**: 对于积分兑换,可能存在一些限制,比如兑换次数、兑换门槛等。源码需...
**动态规划**是一种解决最优化问题的方法论,它通过将复杂的问题分解成一系列简单的子问题,并利用子问题的解来构造原问题的解。在本分类中,我们将详细介绍POJ平台上涉及到动态规划的经典题目。 1. **1011 NTA** ...
淘金币兑换助手2012的出现,解决了用户手动查找可兑换商品、计算抵扣比例等繁琐问题。它具有以下主要特点: 1. **自动搜索**:软件能够自动在淘宝平台上搜索支持全额兑换的淘金币商品,用户无需逐一浏览店铺寻找。 ...
在货币兑换的实践应用问题中,学生需要利用给定的汇率数据进行计算,如计算兑换2000元加拿大元需要多少人民币,以及2万元人民币可以兑换多少美元。这类问题的解决不仅要求学生熟悉汇率,还要求他们能正确运用基本的...
在北师大版的五年级数学教材中,人民币兑换的问题被作为课程内容来培养学生应用数学知识解决实际问题的能力。 在教学目标的设定上,本课程着重让学生掌握小数点位置移动的规律,以及理解人民币的整数兑换,并能够...
在“人民币兑换”这一课时中,我们不仅了解了小数的基本性质,还学习了如何将这些性质应用于实际问题中,提升了我们对数学概念的理解及解决问题的能力。 首先,我们了解了小数点移动的规律。这是一个对日常生活十分...
【港币兑换器】是一款实验性质的Android应用,旨在帮助初学者了解移动应用开发,特别是货币兑换功能的实现。这款应用允许用户将港币转换为...这是一次实践动手的好机会,有助于提升开发者在实际项目中的问题解决能力。
【标题】"在线时间兑换积分插件 for PHPwind7.5.rar" 提供了一个功能强大的解决方案,用于将用户的在线活跃时间转化为积分奖励。这个插件是专为PHPwind7.5论坛系统设计的,旨在激励用户更长时间地参与论坛活动,增加...
在学生初步接触求积、商近似值的概念时,教师应充分利用学生已有的知识基础,引导他们自主探索解决问题的方法。例如,当讨论6.7美元兑换人民币的问题时,学生会意识到需要用到乘法,教师可以指导他们进行计算,然后...
12. 长方形面积与瓷砖问题:第十二题涉及到长方形面积计算,以及瓷砖覆盖面积的计算,还需解决定金和付款问题,以及相遇问题。 13. 平均数计算:第十三题是求全班平均身高的问题,需要用到加权平均数的概念。 14. ...