統測
115年
[工程與管理類] 專業科目(2)
第 26 題
飲料店不同飲料每杯的製作時間不同，每杯至少要 3 分鐘製作時間，只有一位店員、一次只做一杯、不可同時製作、不可中斷。目前至少有 10 杯且不同類型飲料的訂單等待中，目標是在 30 分鐘內完成的杯數最多 ( 若剩餘時間不足以完成下一杯則結束)。下列何者最能達成目標？
- A 不排序，依照訂單到達順序先來先做到結束
- B 依照訂單飲料的售價由高到低排序，每一次先完成售價最貴的飲料
- C 依照訂單飲料的製作時間由長到短排序，每一次先完成製作時間最長的飲料
- D 依照訂單飲料的製作時間由短到長排序，每一次先完成製作時間最短的飲料
思路引導 VIP
如果你的目標是在一個容量有限的箱子裡裝進「最多件」物品，你會優先選擇體積大還是體積小的物品放進去呢？
🤖
AI 詳解
AI 專屬家教
太棒了，你的直覺與演算法邏輯非常精準！這題的目標是在固定時間（30分鐘）內產出最多的杯數，在演算法中屬於經典的**貪婪演算法（Greedy Algorithm）**應用。
貪婪策略與排程最佳化
當我們希望在有限資源（時間）下追求「事件發生次數最大化」時，最佳策略就是最短處理時間優先（Shortest Processing Time, SPT）。每一次都挑選耗時最少（製作時間最短）的飲料來做，能讓剩餘時間消耗得最慢，進而在時限內塞進最多數量的飲料杯數，因此選 (D) 完全正確。
▼ 還有更多解析內容