最少钱币数
【问题描述】
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了6种钱币面值为2、5、10、20、50、100,用来凑
15元,可以用5个2元、1个5元,或者3个5元,或者1个5元、1个10元,等等。显然,最少需要2个钱币才能凑成15元。
你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。
之前使用了贪心法求解,贪心法是有一定条件才能成立的,具体什么条件,这里暂时不探讨,以后有机会我总结一下。
这个问题可以简述为:
如有 int coins[m] 个硬币,需要找零n(任意大的整数)钱币,那么如何做呢?
这就是需要动态规划法了,
假设cNums[i]是记录了需要的最少硬币数来找零i元的。那么如果我们使用面值是x的硬币来找零,那么现在我们就需要 cNums[i] = 1+cNums[i-x];记得i是总钱币数,需要减少x,然后找到了i-x下标,对应之前已经找到的最少钱币数的存储数组的值。
如下面的图:
每次只需要使用一个变量c存储当前行中最小值。12.8updat图表:
例子解说:
这里的初始化值是0,因为要找零0元,只需要0个硬币。
我们有2元7元和3元的硬币值。
当i=2的时候,那么就需要1个2元的硬币,到了3的时候就需要一个3元硬币,到了4需要2个2元硬币。以此类推,到了10可以用5个2元硬币,也可以用一个7元,一个3元,当然也可以先用3元再用7元,顺序不要紧,比较5和2,当然是2个硬币最少,所以最后就是2个硬币就可以找零10元了。
看程序:
int minChangeDP(int coins[], int m, int n, vector<int> &minCoins)
{
if (n<0)
{
return -1;
}
vector<int> cNums(n+1,0);
//注意:这里需要分配好内存
minCoins.resize(n+1);
int min;
int c;
//注意:这里的下标是1到n+1,因为第0个元素默认为零总钱币数,就只需要零张找零
for (int i = 1; i < n+1; i++)
{
min = INT_MAX;
c = 0;
for (int j = 0; j < m; j++)
{
if (coins[j] <= i)
{
//注意:一定要有判断-1的条件,否则结果不正确
//这里的意思是-1代表无法整数硬币找零,即无解!
if (1+cNums[i-coins[j]] < min && cNums[i-coins[j]] != -1)
{
//注意:这里的min和c都是所有零钱比较过之后放入最小值才存在到cNums和minCoins中
min = 1+cNums[i-coins[j]];
c = j;
}
}
}
cNums[i] = min==INT_MAX? -1:min;
minCoins[i] = c;
}
return cNums[n];
}
这里返回的是最少硬币数,其实可以更加强大,已经保存了所有n元以下的最少硬币找零的情况,有兴趣可以修改一下。
还可以输出最终方案呢:12.8 update : 减少coins[]元素个数的参数,不需要。
void makeChanges(int coins[], vector<int> &minCoins, int n)
{
while (n>0)
{
cout<<coins[minCoins[n]]<<"\t";
n = n - coins[minCoins[n]];//minCoins[]是硬币序列coins的下标
}
cout<<endl;
}
也可以输出所有n元一下的最少硬币找零情况。稍微修改一下就可以了。
下面是测试程序:
int main()
{
int i;
int arr1[] = {2};
int arr2[] = {2,7};
int arr3[] = {2,7,3};
int m1 = sizeof(arr1)/sizeof(arr1[0]);
int m2 = sizeof(arr2)/sizeof(arr2[0]);
int m3 = sizeof(arr3)/sizeof(arr3[0]);
//打印0-11元的所有最小硬币数
for (i=0; i < 11; i++)
{
printf("%d ", countDP(arr1, m1, i));
printf("%d ", countDP(arr2, m2, i));
printf("%d ", countDP(arr3, m3, i));
cout<<endl;
}
cout<<endl;
vector<int> minCoins;
cout<<"Minimum changes is:\n";
cout<<minChangeDP(arr3, m3, 999, minCoins);
cout<<endl;
cout<<"The changes we need is:\n";
makeChanges(arr3, minCoins, 999);
cout<<endl;
system("pause");
return 0;
}
运行结果,为了趣味,输出几个大点的方案看看:
10元找零方案:
100元:
下面会是多少元的找零方案呢?
分享到:
相关推荐
Description 设有 n 种不同面值的硬币,各硬币的面值存于数组 T... 对任意钱数0,对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。
对最少硬币兑换问题的算法进行了分析,并给出了实现
2.求解钱币兑换问题 题目描述: 某个国家仅有1分、2分、5分硬币,将钱n(n>=5)兑换成硬币有很 多种兑法,编写实验程序计算出10分钱有多少种兑法,并列出每种 兑换方式。 3.沙漠问题 题目描述: -辆吉普车来到1000km宽的...
设有n种不同面值的硬币,第i种硬币的币值是vk(其中v1=1),重量是wi,i=1,2……n,且现在购买某些总价值为y的商品,需要用这些硬币付款,如果每种钱币使用的个数不限,那么如何选择付款的方法是的付出钱币的总重量最轻?
问题描述:设有 n 种不同的钱币各若干张,可用这 n 种钱币产生许多不同的面值。试 设计一个算法,计算给定的某个面值,能有多少种不同的...结果输出:将计算出的给定面值的不同产生方法种数输出到文件 output.txt。
下面是一个使用C语言实现的贪心算法示例,即“钱币找零问题”,目标是用最少的钱币数量来找零。 **题目:**给定不同面额的钱币和一个总金额,使用贪心算法计算出最少需要多少个钱币来凑出这个总金额。 要求: ...
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了6种钱币面值为2...你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。
对于给定范围、给定钱币面额,借助埃拉托色尼筛法、迪杰斯特拉算法、图的广度优先遍历算法思想,设计了一个快速计算每个数值的最小钱币数量方法,即最少钱币数量筛法来计算平均纸张数量;对于给定范围、给定数量的...
下面是一个使用C语言实现的贪心算法示例,即“钱币找零问题”,目标是用最少的钱币数量来找零。 **题目:**给定不同面额的钱币和一个总金额,使用贪心算法计算出最少需要多少个钱币来凑出这个总金额。 要求: 1、...
一年级下学期数学钱币题-(1).doc
下面是一个使用C语言实现的贪心算法示例,即“钱币找零问题”,目标是用最少的钱币数量来找零。 **题目:**给定不同面额的钱币和一个总金额,使用贪心算法计算出最少需要多少个钱币来凑出这个总金额。 要求: 1、...
行业资料-电子功用-动态电子钱币的介绍分析.rar
主要介绍了java动态规划算法——硬币找零问题,结合实例形式分析了java动态规划算法——硬币找零问题相关原理、实现方法与操作注意事项,需要的朋友可以参考下
蛮力法新手可看一下,超级入门代码,看看入门蛮力法,高手绕路
超市的自动柜员机(POS)要找给顾客数量最少的现金。 若POS机中有面值为2元,1元,5角和1角的钱币,要给顾客找4元6角钱,怎么找?
8595 钱币组合方法数的问题 时间限制:300MS 内存限制:1000K 提交次数:43 通过次数:17 题型: 编程题 语言: 无限制 Description Input 第1行有1个正整数n(1),表示有n种不同的钱币。 第2行有n个数,分别表示每...
给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。 例如,美国硬币面额有1、5、10、25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个...
完整可直接运行的动态规划算法实现和算法分析PPT文档,包括组合钱币、仓库布局、石子划分、彩灯划分和购物等实际问题,全部都是基于动态规划算法实现。本资源包含了以上全部动态问题的完整可直接运行优秀代码,问题...
大班科学领域--认识钱币.pptx
贪心算法——用最少硬币找出n分钱的问题,以及代码。终于解决了