算法笔记：找硬币问题（贪婪算法）C++实现

#include
using namespace std;

//基于贪婪算法的支付函数，每一次首先从当前面值最大的硬币考虑
unsigned ChangeMoney(const unsigned* values, const unsigned& n, unsigned* nums, unsigned money)
{
	unsigned sum = 0;
	for (unsigned i = 0; i < n; i++)
	{
		nums[i] = money / values[i];
		sum += nums[i];
		money -= nums[i] * values[i];
	}
	return sum;
}

int main(void)
{
	unsigned n;
	cout << "请输入硬币的种类数：";
	cin >> n;
	unsigned* values = new unsigned[n];
	cout << "请从大到小输入每种硬币的面值：";
	for (unsigned i = 0; i < n; i++)
	{
		cin >> values[i];
	}
	unsigned money;
	cout << "请输入需要支付的价格：";
	cin >> money;
	if (money < values[n - 1])//如果所需要支付的金额比面额最小的一枚硬币还要少，则无法完成支付
	{
		cout << "无法使用硬币完成支付！" << endl;
		return 0;
	}
	unsigned* nums = new unsigned[n];
	for (unsigned i = 0; i < n; i++)
	{
		nums[i] = 0;
	}
	cout << "最少需要支付的硬币数为：" << ChangeMoney(values, n, nums, money) << endl;
	cout << "各种类型硬币支付的数量为：" << endl;
	for (unsigned i = 0; i < n; i++)
	{
		cout << values[i] << "：" << nums[i] << "\t";
	}
	cout << endl;

	return 0;
}