8.算法入门从零开始——找硬币——贪心

问题:

        假设有四种硬币,面值分别为二角五分、一角、五分和一分。现在要找给顾客六角三分钱,要求找给顾客硬币数量最少。

思路:

        贪心算法是只看眼前最优解而不管全局最优解,所以在选择硬币时,我们首先会选择面额较大的硬币既然要求硬币数量最少,那么就先从硬币面值大的开始找起。即两个二角五分,一个一角、三个一分。

        注:贪心算法只是给出一个近似最优解,并不一定每次都会给出最优解。

代码:

#include<bits/stdc++.h>
using namespace std;
int money=63;//模拟总钱数 
int m1=0;//模拟两角五分 
int m2=0;//模拟一角 
int m3=0;//模拟五分 
int m4=0;//模拟一分 

void sum(){
	m1=money/25;
	money-=m1*25;
	m2=money/10;
	money-=m2*10;
	m3=money/5;
	money-=m3*5;
	m4=money;
}

int main(){
	sum();
	cout<<"两角五分:"<<m1<<"个,一角:"<<m2<<"个,五分"<<m3<<"个,一分"<<m4<<"个";
	return 0;
} 

上一篇:【算法】贪心算法(C++)


下一篇:1071 小赌怡情 (15 分) python