Greedy Algorithm — 貪婪演算法

發表於 更新於 分類於
貪婪演算法（英語：greedy algorithm），又稱貪心演算法，是一種在每一步選擇中都採取在當前狀態下最好或最佳（即最有利）的選擇，從而希望導致結果是最好或最佳的演算法。(引用自wikipedia)

貪婪演算法（英語：greedy algorithm），又稱貪心演算法，是一種在每一步選擇中都採取在當前狀態下最好或最佳（即最有利）的選擇，從而希望導致結果是最好或最佳的演算法。(引用自 wikipedia)

情境 1:小明有個已經養了三年的小豬撲滿裡面，某天他心血來潮把小豬宰了，想把裡面的零錢(一共 29580 元)全部拿去銀行換成鈔票，但是他的皮夾沒辦法放入太多的鈔票，希望銀行可以換給他最少數量的鈔票，因此在兌換的時候必須優先兌換面額最大的鈔票，因此最理想的狀況會是:

  • 1000 元 X 29
  • 500 元 X 1
  • 50 元 X 1
  • 10 元 X3

用 js 來實作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const exchange = (num) => {
  const money = [1000, 500, 100, 50, 10, 5, 1];
  let point = 0;
  const record = [0, 0, 0, 0, 0, 0, 0];
  while (num > 0) {
    if (num >= money[point]) {
      num -= money[point];
      record[point]++;
    } else {
      point++;
    }
  }
  return record;
};

exchange(29580);
//輸出[29, 1, 0, 1, 3, 0, 0]

情境 2:潛入珠寶店的小偷帶了一個後背包可以負重 20kg，因為空間有限，所以他只能挑選最有價值的寶石裝進背包，讓他可以最大化今晚的獲利，可以看到下表有所有的寶石的價格和庫存，在挑選寶石除了選最貴的之外還要考量到重量的問題，那麼，就開始來選擇要優先帶走那些寶石吧!

  1. 先將最貴的一顆鑽石放進背包 (背包剩餘重量 14kg)
  2. 接著把一顆紅寶石放進背包(背包剩餘重量 9kg)
  3. 藍寶石有 2 顆我全都要，通通放進背包(背包剩餘重量 1kg)
  4. 再放一顆祖母綠就好，可…可惡，居然超重了 😢(背包剩餘重量-1kg)
  5. 不甘心的把祖母綠放回去，放進一顆蛋白石(背包剩餘重量 0) 大功告成!

本次行動總收益:1000 萬 x1 + 700 萬 x1+ 500 萬 x2 + 100 萬 x1 = 2800 萬!

像是這類可以利益最大化或是最佳解的的問題很常出現在日常生活中，畢竟大多時候人都是以利益最大化為出發點，思考著該怎麼做才會是最有利的，仔細想想，其實以人類的本性來說，無形之中我們應該用過不少次貪婪演算法了吧!😆