→ LPH66 : 文中也給出了貪心取法的反例: {4,5,6,7,8} 給 2 人 06/06 02:35
→ Arton0306 : 原本還以為greedy是最佳解 感謝! 06/06 12:23
※ 編輯: Arton0306 (220.130.177.154), 06/06/2017 12:23:42
問題：
有n個難易不同的任務，越難的需時越久。現在有k個工人要完成這n個任務，
每個工人一次只能做一個任務，做完才能做下一個，不可分段做，
且每個工人的能力完全相同，解任務的時間完全依據任務本身。
任務本身沒有相依性完全獨立，不同工人可以解不同任務。
現在要問如何分配任務才能在最短時間完成全部任務？
有個直觀的想法是，任何一個工人挑現有未認領的任務中最難的，做完就依
同樣方式選任務，直到所有任務完成。
請問這個方式是否可得最短時間解？是的話要怎麼證明？
不是的話可否舉出一個反例(某一種任務組合)。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.36.190
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1496687025.A.22A.html