貪心演算法

習題預習

1. 給定一個數組，找到最大的子陣列和。
2. 有n個活動，每個活動都有一個開始時間和結束時間。在相同的時間內只能參加一個活動，請問最多能參加多少個活動？
3. 給定一個字符串，判斷是否可以重排該字符串，使得相鄰的字母不同。
4. 給定一個數組，每個元素代表一個氣球的戳破得分，同時將與戳破的氣球相鄰的氣球移除。在不斷戳破氣球的過程中，求最大得分。
5. 將數列切成若干段，使得每段數列中的數字都是單調的，求最少可以切成幾段。

說明知識

貪婪算法（Greedy Algorithms）是一種求解最優解問題的演算法。貪婪算法的基本思想是每一步都選擇當前最好的選擇，決策選擇只考慮當前狀態下對全局最優解的影響，不考慮其他決策的影響。

舉例來說，當我們需要在有限的時間內拿到最多的錢幣，我們可以使用貪婪算法。假設有5枚錢幣，面值分別為1元、2元、5元、10元、20元，我們需要在時間內盡可能收集最多的錢幣。貪婪算法的思路就是每次挑選最大面值的錢幣。若現在已經收集到了15元錢幣，那麼接下來我們只能收集20元的錢幣，以此類推。

另一個例子是人腦大局觀的思維也可被理解為貪婪算法：在鋼琴音樂會中，演奏者通常會把較難的樂章放在前面演奏，這樣可以讓聽眾更加期待、產生興趣，從而更好的抓住觀眾的心。但如果演奏者把所有難的曲子都安排在了前面，則很可能會讓聽眾感到厭煩，這樣反而達不到目的了。所以，合理的貪婪策略是：前面的曲子適當加上一些容易懂的、輕鬆的、好聽的曲目，中間放上一些較為難的曲子，最後再放上一些印象深刻、需要技巧的曲子，這個策略能夠實現讓觀眾逐漸進入異境的效果。

簡而言之，貪婪算法就是通過一個簡單的、每步都選擇當前最好的策略迭代地逼近最優解的演算法，但貪婪策略不一定產生最佳結果，因為貪婪策略的局部最優並不一定等於全局最優。

彙總重點

1. 貪婪算法是一種以貪婪方式選擇最佳選擇的算法。
2. 貪婪算法基於當前最佳選擇，而沒有考慮全局最優解。
3. 貪婪算法通常適用於最佳化問題，其中存在局部最優解，而不是全局最優解。
4. 貪婪算法通常可解決一些NP問題。這些問題需要儘可能地縮小搜索空間。
5. 貪婪算法常常需要與其他算法結合使用，以獲得更好的結果。
6. 貪婪算法不保證總是得到最優解，但是它可以提供快速的解決方案。
7. 貪婪算法的實現通常需要選擇一個合適的啟髮式函數。

知識測驗

1. 電影院的座位（Movie Theater Seating）
   題目描述：假設有一家電影院，他的座位是由X（已被購買的座位）和O（空位）組成，現在需要將已購買的座位重新排列，使得每一個橫排上的相鄰座位之間距離最大化（即保持間距盡量最大）。
   範例輸入：XXOXXOOX
   範例輸出：4

2. 奇偶排序（Odd-Even Sort）
   題目描述：給定一個整數數列，實現一個奇偶排序算法，使得偶數位上的數字一定比奇數位上的小。算法只能使用元素的交換操作，時間複雜度必須小於O(n^2)。
   範例輸入：5 2 1 7 8 3
   範例輸出：2 5 1 8 3 7

3. 無序排列問題 (Unordered Scheduling)
   題目描述：假設有一家餐廳，規定每位客人喝飲料的時間是一樣的，而用餐時間是不同的，為了最大化餐廳的效率，需要找到一個最優的用餐排列方式，排列方式只考慮到顧客的到達順序，不考慮其他條件。
   範例輸入： 10 5 3 12 18 20 25
   範例輸出： 3 5 10 12 18 20 25

4. 分散式等待線程（Distributed Wait Threads）
   題目描述：假設有n個辦公室，每個辦公室中有m個員工，當有人需要打印時，需要先開啟CPU並且連接打印機。但是，當多個人同時要求使用打印機時，CPU會優先處理待機時間較短的人的請求。基於以上條件，要求配置一個算法，以求出需要等待最長的員工的等待時間。
   範例輸入：
   4辦公室
   10, 5, 4, 12員工
   等待時間：2, 5, 1, 3
   範例輸出：5

5. 切割木條（Cutting Wood）
   題目描述：假設有一條木材，需要將它切成n段，切割後每段木材的長度不同，且有一個價格，請問如何切割才能獲取最大價值。
   範例輸入：lengths = [1, 2, 3, 4, 5, 6], prices = [1, 5, 8, 9, 10, 17], n = 6
   範例輸出：22

答案：

1. https://goo.gl/pY6QFC
2. https://goo.gl/bwWhNU
3. https://goo.gl/we4ZPD
4. https://goo.gl/U6Uunx
5. https://goo.gl/rhUTm1