硬币问题

问题如下：

解题思路：

这道题需要用贪心算法来求解，所谓贪心算法就是按照某种规则（贪心策略），不断贪心的选取当前最优解而最终获得整体最优解的算法设计方法。那么这道题我们应该如何用贪心算法来进行求解呢？在使用贪心算法之前，我们首先第一步就是要想出这道题的贪心策略，也就是上面所说的"某种规则"。

其实，这道题的贪心策略实际上不难想出：我们可以按照这样的策略来进行解题：

或者用一句话来总结的话就是：优先使用面值大的硬币。当你使用面值的硬币越大，你所使用的硬币的个数就越少。因此，这道题的贪心策略就是：优先按照面值大的硬币来进行消费。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int moneyvalue[6] = { 1,5,10,50,100,500 };             //代表硬币的面值
int moneycount[6];                                     //代表每种面值硬币的个数
int A;                                                 //代表要支付的钱数
int greedy();                                          //代表要进行贪心算法的函数

int greedy() {
	int i;
	int count;                                            //代表每次硬币的枚数
	int sum = 0;                                          //代表进行支付时，所用硬币的最少枚数
	for (i = 5; i >= 0 ; i--) {
		count = min(A / moneyvalue[i], moneycount[i]);    //代表使用面值尽量大的硬币时，该硬币所用的枚数
		A -= count * moneyvalue[i];                       //使用该硬币进行支付后，要支付的钱数也要对应相减
		sum += count;
	}
	return sum;

}

int main() {
	int i;
	for (i = 0; i < 6; i++) {
		scanf("%d",&moneycount[i]);
	}
	scanf("%d", &A); 
	cout << greedy() << endl;
}

执行结果：

硬币问题

原文：https://www.cnblogs.com/gao79135/p/14250793.html