我要评论贪心法就是遵循某种规则，不断贪心地选取当前最优策略的算法设计方法
硬币问题
有1元、5元、10元、50元、100元、500元的硬币各c、c、c10、c50、c100、c500枚。现在要用这些硬币来支付a元，最少需要多少枚硬币?假定本题至少存在一种支付方案。
限制条件
0 ≤ c1，c5，c10，c50，c100，c500 ≤ 10^9
0 ≤ a ≤ 10^9
样例
思路分析
凭直觉：
首先尽可能多地使用500元硬币;
剩余部分尽可能多地使用100元硬币;
剩余部分尽可能多地使用50元硬币;
剩余部分尽可能多地使用10元硬币;
剩余部分尽可能多地使用5元硬币;
最后的剩余部分使用1元硬币支付。
简言之：优先使用面值大的硬币。
贪心算法，它遵循某种规则,不断地选取当前最优策略
题解
#include<iostream>
using namespace std;
//硬币的面值
const int v[6] = {1,5,10,50,100,500};
//输入
int c[6]; //每种硬币的枚数
int a;
int main(){
//答案
int ans = 0;
//硬币枚数
for(int i = 0 ; i < 6 ; i ++){
scanf("%d",&c[i]);
}
//a
scanf("%d",&a);
for(int i = 5 ; i >= 0 ; i --){
int t = min(a / v[i] ,c[i]); //使用硬币i的枚数
a -= t * v[i];
ans += t;
}
printf("%d\n",ans);
return 0;
}
运行结果
发表评论