[其他] 演算法 greedy algorithm

看板Math作者 (銘銘)時間8年前 (2017/10/25 22:19), 8年前編輯推噓3(3推 0噓 3→)
留言6則, 3人參與, 8年前最新討論串1/1
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
推
10/26 02:22, 8年前 , 1F
原文好像沒有預設greedy solution是不是最佳解耶
10/26 02:22, 1F
→
10/26 02:22, 8年前 , 2F
但根據經驗，greedy應該是optimal，用反證法去證
10/26 02:22, 2F
→
10/26 02:24, 8年前 , 3F
不然就是用那個greedy choice property還有 optimal
10/26 02:24, 3F
→
10/26 02:24, 8年前 , 4F
substructure什麼鬼的特性去說明應該也可
10/26 02:24, 4F
推
10/26 02:40, 8年前 , 5F
如果生產力可以是負的 就很好找了
10/26 02:40, 5F
推
10/26 09:31, 8年前 , 6F
覺得數學歸納法加排序不等式應該可解
10/26 09:31, 6F
‣ 更多 Mingming1258 的文章
文章代碼(AID): #1Py9s1MN (Math)