※ 引述《Raistlinmiao ()》之銘言： : 我記得以前的小謎語裡面有問到 : 如果兩個人要平分一杯牛奶(假設有杯子 該有的都有 細節忽略) : 最公平的方法 就是一個人把牛奶分成兩份 第二個人先挑走一份 恕刪 這個問題很好玩 我大學專題課的時候有接觸到類似的問題 首先問題的定義的是 假設我們要分配某個資源，例如pizza 這塊pizza可能是不均勻的 現在如果有n個人想要分這塊pizza 而每個人對這塊pizza都有自己的measure 例如A喜歡青椒，所以如果他得到的pizza上有很多青椒 即使這塊pizza很小，他仍會覺得很滿足 而我們定義每個人對原始整塊pizza的measure為1 如何找到一個切法使得每個人可以滿足他所得到的pizza 在切法上有一些規定 1.pizza是可以無限分割的 2.如果有n個人，則最多只可切n-1刀，每一刀只能將一塊分成2塊 每個人最多只可切一刀 3.當某一個人在切的時候，不可徵求其他人的意見 4.在某些時候(不是切pizza時)，可能必須要徵詢你的看法 你必須誠實問答，如果有欺騙的行為，也只是影響你自己的權益 如果按照以上的規定，可以找到一個演算法 使得每個人得到1/(2n-2)的pizza(按照他自己的measure) 詳細內容在"How to cut a cake almost fairly" 這篇paper有說明 google上應該找的到 另外，如果對這這一方面的問題很有興趣 還可以考慮閱讀這一本書 "Cake-Cutting Algorithms: Be Fair If You Can" 裡面提供了很多有關於資源分配的演算法 在每個人對資源的評斷標準不同時，如果找到一個分配方法 使得大家都滿意。 這書還蠻有趣的，只有一百多頁 這書是我大學時看的，可能有些內容也記不清楚了 現在書也不在我手邊，如果有錯誤的話，還請見諒 詳細演算法的內容，我回頭查明後再與大家分享。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.187.159.29