資料結構與演算法
以1圓、4圓、6圓3種硬幣支付8圓。以從大硬幣開始盡量使用的貪婪演算法決定時的枚數，與最少枚數的關係，下列何者正確？
- A貪婪演算法也能得到最少的2枚
- B貪婪演算法為3枚，無法得到最少的2枚
- C貪婪演算法為3枚，這就是最少枚數
查看答案與解析
正確答案：B. 貪婪演算法為3枚，無法得到最少的2枚
貪婪演算法先使用1枚6圓，剩下的2圓以2枚1圓支付，共3枚。但若使用2枚4圓，只需2枚。如此可見，貪婪演算法只是累積當下看起來最好的選擇，視硬幣的組合而定，可能不是最佳解。以動態規劃從小金額開始依序建立「支付0圓到8圓各金額所需的最少枚數」的表，就一定能求出最少枚數。另外，像日本硬幣1、5、10、50、100、500圓這樣的組合，貪婪演算法總能得到最少枚數。
- A. 貪婪演算法會先選6圓，因此到不了2枚4圓的組合。
- B. 正確。貪婪演算法為 6 + 1 + 1 共3枚，最少為 4 + 4 共2枚。
- C. 使用2枚4圓只需2枚，因此3枚不是最少。