為什麼這篇貪婪演算法證明鄉民發文收入到精華區:因為在貪婪演算法證明這個討論話題中,有許多相關的文章在討論,這篇最有參考價值!作者Mingming1258 (銘銘)看板Math標題[其他] 演算法 greedy algorit...
貪婪演算法證明 在 Jying Chang Instagram 的精選貼文
2021-04-04 17:46:01
#purrreads Susan Sontag《論攝影》 「把照片變得超現實的,不是別的,而是照片做為來自過去信息這無可辯駁的感染力,以及照片對社會地位作出種種提示時的具體性。」 這本書曾在大學時期陪伴我許多時光,也被我帶去加拿大當作閒暇時間的讀物。但隨著年紀漸長、工作忙碌,便漸漸...
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