【问题描述】
这是一个古老而又经典的问题。 用给定的几种钱币凑成某个钱数,一般而言有多种方式。 例
如:给定了 6 种钱币面值为 2、 10、 50、
5、 20、 100,用来凑 15 元,可以用 5 个 2 元、 个 5 元,
1
或者 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
12
0
【样例输出】
2
Impossible
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－总结的分割线－－－－－－－－－－－－－－－－－－－－－－－－－－
总结：
1， 在写程序的时候发现， 虽然我学过一点STL,但在用起来的时候非常的不熟练，需要边查资料边写，以前大多用c语言写程序，现在有必要多写一点c++程序，多用STL，提高编程能力。
2，这个程序的查找还可以优化一下，可以用二分法查找，找到小于或者剩余的钱数。
3，题目要求的输入限制没有检测。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
程序代码：
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
bool greater(const int &i, const int &j);
class money {
public:
money(vector<int> &m);
~money();
void show(int value);
private:
vector<int> m_money;
};
money::money(vector<int> &m): m_money(m)
{
sort(m_money.begin(), m_money.end(), greater);
}
money::~money()
{
}
bool greater(const int &i, const int &j)
{
return i > j;
}
void money::show(int value)
{
size_t count = 0;
while (value > 0) {
vector<int>::iterator i = m_money.begin();
while (i != m_money.end()) {
if (*i > value) {
i++;
}
else {
break;
}
}
if (i == m_money.end()) {
printf("Impossible\n");
return;
}
count += value / *i;
value = value % *i;
}
printf("%d\n", count);
}
int main(int argc, char *argv[])
{
vector<int> input;
int value;
int num;
int n;
scanf("%d", &value);
scanf("%d", &num);
while(true) {
scanf("%d", &n);
if (n == 0) {
break;
}
if (num > 0) {
input.push_back(n);
num--;
}
}
money m(input);
m.show(value);
return 0;
}