问题在于:给出4组大小为A,B,C和D的学生,以及总共k个伴侣,设计一种算法,以近乎相等的比例为学生分配伴侣.
您不能只给组k*A/N,k*B/N,k*C/N,k*D/N伴侣,因为伴侣的数量必须是正整数.你不能只是圆,因为那时你可能得不到合适数量的伴侣.所以我的想法是你扔出小数部分,并给每个组赋予整数部分,所以做整数除法.然后你可能会留下一些陪伴者,但最多只有3个,所以把它们交给剩下最多的群体.
然后,采访者指出这是一个问题.如果你添加另一个伴侣,所以将k增加到k + 1,那么可能会发生其中一个组实际上以这种方式失去伴侣.她给了我一个例子,但我不记得了.
任何人都可以想出一个避免这个问题的算法吗？
您尝试解决的问题通常称为分配问题或投票分配问题.这与将美国众议院的席位数分配给每个州的问题相同.
您的方法(称为汉密尔顿方法或最大余数的方法)无法具有的鲁棒性问题被称为阿拉巴马悖论.根据维基百科的文章,"阿拉巴马州悖论发现于1880年,当时发现增加席位总数会使阿拉巴马州的份额从8减少到7".
从历史上看,美国至少使用了四种不同的方法:Jefferson方法,Hamilton方法,Webster方法以及 自1941年以来使用的当前Huntington-Hill方法.
后面这些方法背后的想法如下.让D = N/k,总人口除以座位/监护人的数量.然后让d = D,并修改,d直到四舍五入k_i = round(G_i/d)
加上正确的席位数,即
圆(G_1/d)+圆(G_2/d)+ ... +圆(G_m/d)= k
问题在于函数的round工作原理.韦伯斯特的方法通常意义上说:弱于.5上升,严格低于.5下降,这与使用算术平均值非常相似.Huntington-Hill方法基于使用几何平均值的想法.有这些方法中的一个很好的总结
在这里.请注意,所有这些除数算法都存在缺陷,因为它们违反了配额规则:状态不能保证至少得到
floor(G_m/D)代表.
如果你想更多地玩这个,有一篇关于切割结的完美文章,包括历史,方程式和有趣的小程序.