首页 / 软件开发 / 数据结构与算法 / 编程算法之硬币问题 代码（C）

编程算法之硬币问题 代码（C）2015-10-28题目: 有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
", ans）;}};int main（void）{Program P;P.solve（）;return 0;}

输出:

result = 6

作者：csdn博客 Mystra