计算最少钱币数C++程序代码。

最少钱币数:
【问题描述】
这是一个古老而又经典的问题。         用给定的几种钱币凑成某个钱数,一般而言有多种方式。           例
如:给定了 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;	
}

计算最少钱币数C++程序代码。,古老的榕树,5-wow.com