问题是：给定 4 组大小为 A、B、C 和 D 的学生，以及总共 k 个伴侣，设计一种算法，以几乎相等的比例将伴侣分配给学生。
您不能只给组 k*A/N、k*B/N、k*C/N、k*D/N 伴侣，因为伴侣的数量必须是正整数。而且你不能只是四舍五入，因为那样你可能得不到正确数量的伴侣。所以我的想法是你把小数部分扔掉，把整数部分给每个组，整数除法也是如此。那么你可能有一些剩余的伴侣，但最多3个，所以把它们分配给剩余最多的组。
然后，面试官指出这个有问题。如果您添加另一个伴侣，因此将 k 增加到 k+1，那么其中一个组实际上可能会以这种方式失去一个伴侣。她给了我一个例子，但我不记得了。
谁能想出一个避免这个问题的算法？
您尝试解决的问题通常称为分配问题或选票分配问题。这与将美国众议院的席位数量分配给每个州是同一个问题。
您的方法（称为 Hamilton 方法或最大余数方法）未能解决的稳健性问题被称为Alabama Paradox。来自维基百科的文章，“阿拉巴马悖论是在 1880 年发现的，当时发现增加席位总数会使阿拉巴马州的份额从 8 个减少到 7 个。”
从历史上看，美国至少使用了四种不同的方法：Jefferson 方法、Hamilton 方法、Webster 方法和 自 1941 年以来使用的当前Huntington-Hill 方法。
后面这些方法背后的想法如下。让D = N/k，总人口除以座位/陪护人数。然后 let d = D，并修改d直到四舍五入k_i = round(G_i/d)
加起来正确的座位数，即
回合（G_1/d）+回合（G_2/d）+ ... +回合（G_m/d）= k
关键在于函数的round工作方式。Webster 的方法在通常意义上进行：弱高于 0.5 上升，严格低于 0.5 下降，这很像使用算术平均值。Huntington-Hill 方法基于使用几何平均值的思想。这里有这些方法的一个很好的总结
。请注意，所有这些除数算法都存在缺陷，因为它们违反了配额规则：不能保证一个州至少获得
floor(G_m/D)代表。
如果你想更多地玩这个，在Cut The Knot上有一篇很棒的文章，里面有历史、方程式和有趣的小程序。
给定 4 组大小为 A、B、C 和 D 的学生以及总共 k 个伴侣，设计一种算法，以几乎相等的比例将伴侣分配给学生。
这是一个非常简单地解决问题的算法：
从每组 0 名伴侣的分配开始。如果任何组中没有学生，则丢弃该组，因为不会为这样的组分配监护人。
如果分配的伴侣总数等于 k，那么我们就完成了。
将一名监护人分配给一组。接受监护人的小组是每个学生的监护人比例最低的小组。在平局的情况下，从每个学生的监护人比例最低的小组中选择学生最多的小组。如果仍有平局，则从选定的组中选择按字母顺序排在第一位的组。
转到第 2 步。
它做出明确的确定性分配。在数值允许的范围内，比例将几乎相等。增加 k 不会减少对任何组的分配，因为它实际上只会导致发生额外的迭代，并且没有迭代会减少任何组的分配。
相同大小的两组可能有不同数量的伴侣，但如果不重新说明问题以允许对 k 进行修改，则无法纠正这种情况。在任何情况下，两个大小相同的组的分配差异都不会超过 1。
其他答案中用于将表示分配给状态的所有算法都不必要地复杂，并且旨在最大限度地减少执行的计算步骤的数量（通过进行数值计算而不是增量分配）。我给出的算法在计算机上运行时非常简单。