※ 引述《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