題組內容
二、假設收銀機內銅板的集合 S={$50, $20, $20, $15, $10, $2, $1, $1, $1},而
預計找錢給顧客的金額 W=$75。
(一)請設計一個 Greedy(貪婪)的演算 法,來解決找錢給顧客的問題,使得找給顧客金額 W 所使用的銅板數量 最少,並依此 Greedy 的演算法列出找給顧客金額 W=$75 的過程。 (15 分)
詳解 (共 1 筆)
詳解
貪婪法
1.將幣值由大到小排序
2.將找錢額度依幣值大小扣除
3.若遇到不足額,往剩餘可扣的最大幣值扣除