Response to 110篇的問題

因為比較長XD

Hi Tony,
打了一下解釋發現不是很短，我乾脆新開一篇來解釋好了~

原文章：
從LeetCode學演算法 — 110 Array (16) / Greedy Algorithm (1)
0881. Boats to Save People (Medium)

提問：

這是個好問題，
貪婪演算法的核心觀念是每次取當前最佳解，以讓全局能達到最佳解。
以這題來說，有幾個重要的前提條件：

1. 所有人都一定能搭上船(每個人的重量至少<=limit)
2. 假設配不到對，就要自己搭一艘船
3. 一艘船最多2個人

所以看這題其實要拆成兩個步驟：
1. 最重的人不一定能湊組，所以能湊就湊，
否則自己就要一艘船，以能湊到為準

2. 最輕的人上船要盡可能搭配的越重的人越好

綜合以上的話，就會做出文章內敘述的選擇。

你會說，這樣好像沒有局部最佳解阿？
但我們要思考一下這裡我們的目標是什麼，
目標應該是花盡可能少的船隻數量以載完所有人，
在這個前提條件下，拿最輕的人去組到最重的人，
由於不論怎樣都能讓已成定局的組留給後面組到的機會較好。
(也就是輕的人本來是一艘負重比較不划算的狀況，
能湊到2人一艘的狀況盡可能配重一點)

假定今天不但要求盡可能少船隻，
還要求盡可能越多艘船是剛好塞到負重上限的話，
則會比較接近Knapsack problem，
這樣的話可能就要改成用動態規劃來計算了。

總結一下，
這題我們用的方式是先排序後，
從最重的人開始配組，
並且在能配組的狀況下，讓當前最輕的人和其搭配，
以求後面次輕的人能得到比最重再輕一些的組合，得以2人一艘，
利用這個方式可以將時間複雜度壓到O(NlogN)，
因為除了排序外，
分組檢查的時候每次只需要檢查一個組合的可能性就好了。
因此它貪婪的方式是拿最輕去吃盡可能重的搭配，
而不是求把重量壓到limit。

我相信盡可能把船塞到limit應該還是可以得到正確的解，
只是時間複雜度可能會高一點就是了。

希望這樣有回答清楚你的問題~