C++ 硬币问题（贪心算法）

有1元，5元，10元，50元，100元，500元的硬币各从c1，c5，c10，c50，c100，c500枚，现在要用这些硬币支付A元，最少需要多少枚硬币？

本题利用贪心算法进行求解，即首先考虑使用最大面值的硬币，若不符合条件则使用较小面值的硬币。代码以及注释如下

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define Pi 3.14;
using namespace std;
int main()
{
	int numb[6],money,sum=0;
	int coins[6] = { 1,5,10,50,100,500 };
	for (int i = 0; i < 6; i++)
	{
		cin >> numb[i];
	}
	cin >> money;
	for (int i = 5; money > 0; i--)
	{
		int count = numb[i];//记录当前面值硬币的个数
		int a=0;//记录商
		if (money > coins[i])//若所求值大于当前面值
		{
			a = money / coins[i];//求出理想情况下所需硬币的个数
			if (a > count)//如果现有硬币小于理想情况
			{
				sum += count;//硬币的总个数 需要加上 当前面值现有硬币的个数
				money -= count * coins[i];//求出剩余的面值
			}
			else//现有硬币符合理想情况
			{
				sum += a;//硬币的总个数 需要加上 理想情况下 需要该面值硬币的个数
				money -= a * coins[i];//求出剩余的面值
			}
			
		}
	}
	cout << sum << endl;//写出总个数
}

样例：

输入

3 2 1 3 0 2

620

输出

6