何為貪心算法
現(xiàn)在的貨幣只有 25 分赵抢、20分骗奖、10 分确徙、5 分和 1 分四種硬幣,怎么樣過(guò)用最少的硬幣湊夠41分錢(qián)?
貪心答案 25,10,5,1
正確答案 20 20 1
優(yōu)缺點(diǎn)：
優(yōu):簡(jiǎn)單，高效执桌，省去了為了找最優(yōu)解可能需要窮舉操作鄙皇，通常作為其它算法的輔助算法來(lái)使用；
缺:不從總體上考慮其它可能情況仰挣，每次選取局部最優(yōu)解伴逸，不再進(jìn)行回溯處理，所以很少情況下得到最優(yōu)解膘壶。
代碼示例
int sum_money=41;
int num_25=0,num_10=0,num_5=0,num_1=0;
//不斷嘗試每一種硬幣
while(money>=TWENTYFINEFEN) { num_25++; sum_money -=TWENTYFINEFEN; }
while(money>=TENFEN) { num_10++; sum_money -=TENFEN; }
while(money>=FIVEFEN) { num_5++; sum_money -=FIVEFEN; }
while(money>=ONEFEN) { num_1++; sum_money -=ONEFEN; }
return 0;
練習(xí)題目-leetcode
452題 455題 605題
