最少钱币数 题目和答案
【问题描述】
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了6种钱币面值为2、5、10、20、50、100,用来凑
15元,可以用5个2元、1个5元,或者3个5元,或者1个5元、1个10元,等等。显然,最少需要2个钱币才能凑成15元。
你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。
【要求】
【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M(1 <= M<= 2000,整数),接着的一行中,第一个整数K(1
<= K<= 10)表示币种个数,随后是K个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。
【数据输出】每个测试用例输出一行,即凑成钱数值M最少需要的钱币个数。如果凑钱失败,输出“Impossible”。你可以假设,每种待凑钱币的数量是无限多的。
【样例输入】
15
6 2 5 10 20 50 100
1
1 2
0
【样例输出】
2
Impossible
很久之前在网上参考了下,写了个程序,现在重新看下,觉得写得真的不好,献丑了。
正确的解法应该是使用动态规划法,请参看我另外一篇博客:
http://blog.csdn.net/kenden23/article/details/16864987
这里使用贪心法,贪心法得出的只能是近似最优解,也可能有解也没有找到,所以使用贪心法要非常小心,注意贪心法成立的条件,比如赫尔曼树就是可以的。我也没有到网上做这道题的Online judge,所以也许这里不一定能通过online judge,但是这里的贪心法使用应该是不会有错的了。
感谢 小叶GIS指出。如果需要正确解法请看我的另一篇动态规划法解法吧。
这里更新一下贪心法,程序简洁一点,如果需要更好的解,当然也更加难了,请移玉步到我另外一篇博客。
#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
using namespace std;
int check(vector<int> &coins, int n)
{
if (n < 0) return -1;
if (n == 0) return 0;
sort(coins.begin(),coins.end(),greater_equal<int>());
int cNums = -1;
for (auto x: coins)
{
if(n - x >= 0)
{
n -= x;
cNums ++;
}
}
return cNums;
}
int main() {
vector<int> coins;
int n = 0;
int m = 0;
cin>>m;
while (cin>>n)
{
coins.push_back(n);
if(cin.get() == '\n')
break;
}
int changes = check(coins, m);
if(changes == -1)
cout<<"Impossible!\n";
else cout<<changes<<endl;
system("pause");
return 0;
}
分享到:
相关推荐
这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数,一般而言有多种方式。例如:给定了6种钱币面值为2...你的任务就是,给定若干个互不相同的钱币面值,编程计算,最少需要多少个钱币才能凑成某个给出的钱数。
对于给定范围、给定钱币面额,借助埃拉托色尼筛法、迪杰斯特拉算法、图的广度优先遍历算法思想,设计了一个快速计算每个数值的最小钱币数量方法,即最少钱币数量筛法来计算平均纸张数量;对于给定范围、给定数量的...
Description 设有 n 种不同面值的硬币,各硬币的面值存于数组 T... 对任意钱数0,对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。
贪心算法——用最少硬币找出n分钱的问题,以及代码。终于解决了
minCoins函数使用贪心算法来计算凑出给定金额所需的最少钱币数量。它从最大的钱币面额开始,尽可能多地使用每个面额的钱币,直到凑出总金额或没有更多的钱币可以使用。 请注意,贪心算法并不总是能得到全局最优解,...
minCoins函数使用贪心算法来计算凑出给定金额所需的最少钱币数量。它从最大的钱币面额开始,尽可能多地使用每个面额的钱币,直到凑出总金额或没有更多的钱币可以使用。 请注意,贪心算法并不总是能得到全局最优解,...
minCoins函数使用贪心算法来计算凑出给定金额所需的最少钱币数量。它从最大的钱币面额开始,尽可能多地使用每个面额的钱币,直到凑出总金额或没有更多的钱币可以使用。 请注意,贪心算法并不总是能得到全局最优解,...
使用各种面值的硬币,现用这些硬币找钱 对任意钱数,用最少钱币找钱的方法
2.求解钱币兑换问题 题目描述: 某个国家仅有1分、2分、5分硬币,将钱n(n>=5)兑换成硬币有很 多种兑法,编写实验程序计算出10分钱有多少种兑法,并列出每种 兑换方式。 3.沙漠问题 题目描述: -辆吉普车来到1000km宽的...
大数相加的代码,才写的,最近开始做的oj.不好的请多多包涵!
提供最新C面试题:写一个函数,传入参数为...返回值为买家最少付出的钱的张数int get MoneyNum(int iInputMoney)例如:买家应付351元,最少张数为5.备注:可支付的钱币只有100、50、10、5、1不考虑2、20以及小数部分。
算法的一道题目,最少硬币问题,题目要求是由文件input.txt提供输入数据,文件的第1行中只有1个整数给出 的值,第2行起每行2个数,分别是 和 。最后1行是要找到钱数 。
VISUAL C++MFC编程实例 希望对大家有用!
通过亲测,以实现最小硬币问题算法的C文件
给定一组硬币的面额,以及要找零的钱数,计算出符合找零钱数的最少硬币数量。 例如,美国硬币面额有1、5、10、25这四种面额,如果要找36美分的零钱,则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个...
//设有6种不同面值的硬币,各硬币的面值分别为5分、1角、2角、5角、1元和2元。 //现在要用这些面值的硬币来购物和找钱。购物时可以使用的各种面值的硬币个数 ...//额,计算使用硬币个数最少的交易方案。
用贪心算法来解决贪心算法 【找零钱问题】一个小孩买了价值为33美分的糖,并将1...售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。
4.7假设零钱系统的币值是{1,p,p^2,……,p^n},p>1,且每个钱币的重量都等于1,设计一个最坏情况下时间复杂度最低的算法,使得对任何钱数y,该算法得到的零钱个数最少,说明算法的主要设计思想,证明它的正确性,并给...
算法设计与分析 零钱个数最少问题 ...设计一个最坏情况下时间复杂度最低的算法,使得对任何钱数y,该算法得到的零钱个数最少。说明算法的主要设计思想,证明他的正确性,并给出最坏情况下的时间复杂度。
对最少硬币兑换问题的算法进行了分析,并给出了实现