硬币问题 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 有1, 5, 10, 50, 100, 500元硬币各若干枚, 现在要用这些硬币来支付A元, 最少需要多少枚硬币?

假定本题至少存在一种支付方案.

使用贪心算法, 优先选用最大的硬币, 并不断的调整硬币的数量.

代码:

/*
 * main.cpp
 *
 *  Created on: 2014.7.17
 *      Author: spike
 */

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>
#include <limits.h>

#include <utility>
#include <queue>

using namespace std;

class Program {
	const int V[6] = {1, 5, 10, 50, 100, 500};
	int C[6] = {3, 2, 1, 3, 0, 2};
	int A = 620;

public:
	void solve() {
		int ans = 0;
		for (int i=5; i>=0; i--) {
			int t = min(A/V[i], C[i]);
			A -= t*V[i];
			ans += t;
		}
		printf("result = %d\n", ans);
	}
};


int main(void)
{
	Program P;
	P.solve();
    return 0;
}

result = 6