s***e
发帖数: 911 | 1 昨天和印度人聊天,他说:
有一块饼, 要寻求满意分配. 满意的定义个人心中定义不同. 怎么办?
两人(A,B)分, 显然有满意操作:
A切, B先选;
他的问题是, 3人分一个饼, 存在不存在满意操作完全分配这块饼, 而且是在有限步骤
之内? | h******d
发帖数: 66 | 2
有啊! 这问题偶以前看过解答. N个人分一块饼, 可以这么做: 一个人拿着根线
从饼的这一边开始平移至饼的另一边, 等达到某人心目中的1/N饼时, 他就喊一
句:"停!", 于是那块归他, 其余的人再来分剩下的饼.
或者, 可以这样: 每个人从公共起点处先标出他所认为的1/N处, 标得最少的就
沿他所标处切开给他, 剩下的人继续标.
如果每个人的份额不同, 只要每个人要的都是有理数块饼, 同样可以这么做.
比如第i人的份额为Ai, A1+A2+...+AN = 1, Ai为有理数, 则存在C使得Ai/C均
为整数. 每次竞标小块C就行了. 第i人有Ai/C次竞标机会.
【在 s***e 的大作中提到】
: 昨天和印度人聊天,他说:
: 有一块饼, 要寻求满意分配. 满意的定义个人心中定义不同. 怎么办?
: 两人(A,B)分, 显然有满意操作:
: A切, B先选;
: 他的问题是, 3人分一个饼, 存在不存在满意操作完全分配这块饼, 而且是在有限步骤
: 之内?
|
|
