[其他] 演算法 greedy algorithm

[Mingming1258 (銘銘)]

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是不是最佳解耶
→ alan23273850: 但根據經驗，greedy應該是optimal，用反證法去證
→ alan23273850: 不然就是用那個greedy choice property還有 optimal
→ alan23273850: substructure什麼鬼的特性去說明應該也可
推 gj942l41l4  : 如果生產力可以是負的  就很好找了
推 agga        : 覺得數學歸納法加排序不等式應該可解