//这是一个贪心算法的例子:找硬币问题 
#include<iostream>
using namespace std;
int amount,coins[]={1,2,5,10,20,50,100};//硬币面值数组（已排序）
constint cointypes=7;//硬币种类数量
int greedyCoinChange(int amount){
	int count=0;
	for(int i=cointypes-1;i>=0;i--){//从最大面值开始尝试
		while(amount>=coins[i]){//当前面值最多能用多少枚
			amount-=coins[i],count++;
			cout<<"使用一枚"<<coins[i]<<"元硬币"<<endl;
		}
	}
	return count;
}
int main(){
	cout<<"请输入需要找零的金额：";
	cin>>amount;
	if(amount<=0){
		cout<<"金额必须为正数！"<<endl;
		return 1;
	}
	cout<<"\n找零方案："<<endl;
	int coinCount=greedyCoinChange(amount);
	cout<<"\n总共需要"<<coinCount<<"枚硬币"<<endl;
	return 0;
}