為什麼這篇貪婪演算法例子鄉民發文收入到精華區：因為在貪婪演算法例子這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者Mingming1258 (銘銘)看板Math標題[其他] 演算法 greedy algorit...
https://www.reddit.com/r/askmath/comments/78mdwy/greedy_algorithm/
稍微翻成中文
有3n個人，每個人都有不同的生產力p1,p2...p3n，3個一組分成n組，一組的生產力就是3
個人生產力乘積，試圖找出最好的分組模式讓生產力總和最大
greedy algorithm就是把3n個人依生產力排序，最大到第3一組，第4到第6一組，依此類推
greedy algorithm分出的組個別的生產力訂為 r1,r2...rn (r1>=r2>=...>=rn)
最佳解(正解)為 q1,q2...qn (q1>=q2>=.....>=qn)
1.找出一個greedy algorithm的解不是最佳解的例子
r1+....+rn =/= q1+...+qn
2.證明3(r1+...+rn)>=q1+...+qn
我覺得greedy algorithm的解就是最佳解了欸...有人會解嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.100
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1508941185.A.597.html
※ 編輯: Mingming1258 (140.112.25.100), 10/25/2017 22:21:22
推 alan23273850: 原文好像沒有預設greedy solution是不是最佳解耶 10/26 02:22
→ alan23273850: 但根據經驗，greedy應該是optimal，用反證法去證 10/26 02:22
→ alan23273850: 不然就是用那個greedy choice property還有 optimal 10/26 02:24
→ alan23273850: substructure什麼鬼的特性去說明應該也可 10/26 02:24
推 gj942l41l4 : 如果生產力可以是負的 就很好找了 10/26 02:40
推 agga : 覺得數學歸納法加排序不等式應該可解 10/26 09:31