在現實生活中,常常遇到找零問題,假設有數目不限的面值為20,10,5,1的硬幣。 給出需要找零數,求找零方案,要求:使用數目最少的硬幣。
對於這類問題,貪心演算法採取的方式是找錢時,總是選取可供找錢的硬幣的最大值。例如,需要找錢數為25時,找錢方式為20+5,而不是10+10+5。
貪心演算法還是很常見的演算法之一,這是由於它簡單易行,建構貪心策略不是很困難。本文我們就和大家分享JS使用貪心演算法解決找零問題範例。
可惜的是,它需要證明後才能真正運用到題目的演算法中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
結果是:
1 2 |
|
要說明的是,在某些情況下,找零錢問題使用貪心演算法並不能得到整體最優解,其結果可能只是最優解的很好近似。
例如,如果提供找零的面值是11,5,1,找零15。
使用貪心演算法找零方式為11+1+1+1+1,需要五枚硬幣而最優解為5+5+5,只需要3枚硬幣。
相關推薦:
以上是JS如何運用貪心演算法解決找零問題的詳細內容。更多資訊請關注PHP中文網其他相關文章!