200902网友练习《求的分配问题》

wangerpang

一共有N个球。其中，每个球上都印有编号，编号为1，2，……，M中的一个。同一编号的球允许重复，且重复个数任意。现在有X个容器，每个容器的容量Y不等。现在要把这N个球尽可能均匀地分配到X个容器中，分配过程要求满足以下条件：[N为可趋于正无穷的整数，M，X，Y均为>0的整数]
1、公平性。即分配完毕后，每个容器中的球的个数与总球数之比和该容器容量与总容器容量之比相同。
2、排它性。印有同一编号的球不允许放置到同一容器中，即每个容器中不允许出现编号同为s的球。
3、动态性。容器个数可以动态增加或减少。当增加新容器时，要求把旧容器中的球移到新添加的容器中。总的移动的球的个数要求最少，且也要满足条件1和条件2。当减少容器时，要求把该容器中的球全部取出再均匀地放置到剩余的容器中。总的移动的球的个数要求最少，且也要满足条件1和条件2。
例：现有20个球，编号分别为1，1，1，2，2，3，3，4，4，4，5，5，6，6，7，7，7，8，8，8。要放到4个容器中，每个容器的容量为4。则分配过程如下（按照上述条件人为地分配）：
容器A：1-2-4-6-7
容器B：1-3-4-6-8
容器C：1-3-5-7-8
容器D：2-4-5-7-8
若增加新容器E，则将容器A-D中的球取出一部分放置到容器E中，取的球为4个（最少）且满足条件1、2。
容器A：1-0-4-6-7
容器B：0-3-4-6-8
容器C：1-0-5-7-8
容器D：2-4-5-0-8
容器E：2-1-3-7
(0表示已取走)
若减少容器C，则将C中的球取出放置到A、B、D中，为满足条件1、2，必要时可能需要从容器A、B、D中进行球的置换，但总的移动个数一定要最少。可能的分配方案为：
容器A：1-2-4-6-7-3-8
容器B：1-3-4-6-8-5-7
容器C：1-3-5-7-8
容器D：2-4-5-7-8-1
寻求此分配问题的数学模型。为了描述方便，只要满足条件1、2、3，各位前辈可以自行引入其它的定义与约束。条件1也可以理解为统计意义上的平均。
为简化问题，也可将此问题分解成几个小模型分别求解。1、可先考虑每个容器容量相等的情况，即分配完毕后，每个容器中的球数相等（趋于平均），然后再考虑每个容器容量不等的情况。2、可先考虑同一编号球的重复个数固定的情况，即所有球的重复个数相同，然后在考虑每个球重复数不固定的情况。3、可以把1与2混合起来考虑，然后在复杂化。
我的解法（能力有限，只能想到这里，抛砖引玉了）：
设球的最大副本个数为n（即某编号为s的球有n个，其它编号球的重复个数都不大于n）;设容器个数为y,且n<y；设r为同编号球组中的相对编号，即有5个编号为s的球，则r为1，2，3，4，5。设m为球的编号，则二元组<m,r>就可以唯一的标识出一个球。二元组中，同编号球的m值相同，但r不相同。现把组编号为m的球随机地对应容器y的一个排列，这样就可以保证条件1和2满足。
设z=hash_func（m,r,y），其中，z>0且z<y；hash_func（m,r,y）为一个随机函数。则z就是<m,r>将要放入的容器。

不知道各位前辈有没有什么想法？能给出证明过程，从理论上证明条件1，2，3的满足最好了。

evanlingxp

关注～！~~!!

mnpfc

注意到这个帖子了

wfhe

dou lai guan zhu yi xia