为学生分配监护人的强大算法
问题是：给定 4 组大小分别为 A、B、C 和 D 的学生，以及总共 k 个监护人，请设计一种算法，以几乎相等的比例为学生分配监护人。
你不能只给 k*A/N、k*B/N、k*C/N、k*D/N 分子伴侣，因为分子伴侣的数量必须是正整数。而且你不能只是轮流，因为那样你可能得不到正确数量的陪伴者。所以我的想法是你扔掉小数部分，并将整数部分交给每个组，所以进行整数除法。那么你可能会剩下一些伴侣，但最多 3 个，所以把它们给剩余最多的组。
然后面试官就指出这个是有问题的。如果添加另一个伴侣，将 k 增加到 k+1，那么其中一个组实际上可能会以这种方式失去一个伴侣。她给了我一个例子，但我不记得了。
谁能想出一种算法来避免这个问题？
Here's the problem: Given 4 groups of students of sizes A, B, C and D, and a total of k chaperones, devise an algorithm for assigning chaperones to students in near-equal proportions.
You can't just give the groups k*A/N, k*B/N, k*C/N, k*D/N chaperones, because the number of chaperones has to be a positive integer. And you can't just round, because then you might not get the right number of chaperones. So my idea is that you throw out the fractional part, and give the integer part to each group, so do integer division. Then you might have some left over chaperones, but at most 3, so give them to the groups with the biggest remainders.
Then, the interviewer pointed out that there's a problem with this. If you add another chaperone, so increase k to k+1, then it can happen that one of the groups actually loses a chaperone this way. She gave me an example, but I don't remember it.
Can anyone come up with an algorithm that avoids this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您试图解决的问题通常被称为
分配问题或选票分配问题。这是一样的
美国众议院席位分配问题
各州的代表。
您的方法（称为汉密尔顿方法）的鲁棒性问题
方法或最大余数的方法）不能被称为
阿拉巴马州
悖论。从
维基百科文章，“阿拉巴马悖论于 1880 年被发现，当时
结果发现，增加座位总数会减少
阿拉巴马州的比例从 8 增至 7。”
历史上，美国至少使用过四种不同的方法：
杰斐逊法、汉密尔顿法、韦伯斯特法和
当前 亨廷顿山
方法
自 1941 年起使用。
后面这些方法背后的想法如下。让
D = N/k，总人口除以座位/陪同人员的数量。然后
让
d = D，并修改d直到舍入k_i = round(G_i/d)加起来就是正确的座位数，即
round(G_1/d) + round(G_2/d) + ... + round(G_m/d) = k
问题在于函数 <代码>圆形有效。韦伯斯特的方法
通常意义上的回合：微弱高于 0.5 上升，严格低于 0.5
向下，这很像使用算术平均值。这
Huntington-Hill 方法基于使用几何平均值的思想
反而。这些方法有一个很好的总结
此处。笔记
所有这些除数算法都有缺陷，因为它们违反了
配额规则：一个州不能保证至少获得
地板(G_m/D)代表。如果你想更多地尝试这个，有一个很棒的
关于此的文章 Cut The
结完成
历史、方程式和有趣的小程序。
The problem you're trying to solve is generally known as an
apportionment problem or vote allocation problem. This is the same
problem as assigning the number of seats in the US House of
Representatives to each state.
The problem of robustness that your approach (known as Hamilton's
method or the method of largest remainder) fails to have is known as
the Alabama
Paradox. From the
Wikipedia article, "The Alabama paradox was discovered in 1880, when
it was found that increasing the total number of seats would decrease
Alabama's share from 8 to 7."
Historically, at least four different methods have been used in US:
Jefferson's method, Hamilton's method, Webster's method and the
current Huntington-Hill's
method
used since 1941.
The idea behind these latter methods is the following. Let
D = N/k,the total population divided by the number of seats/chaperones. Then
let
d = D, and modifyduntil the roundingk_i = round(G_i/d)adds up to the correct number of seats, i.e.
round(G_1/d) + round(G_2/d) + ... + round(G_m/d) = k
The catch is in how the function
roundworks. Webster's approachrounds in the usual sense: weakly above .5 go up and strictly below .5
go down, which is rather much like using an arithmetic mean. The
Huntington-Hill method is based on the idea of using a geometric mean
instead. There is a nice summary of these methods
here. Note
that all of these divisor algorithms are flawed in that they violate
the Quota Rule: a state is not guaranteed to get at least
floor(G_m/D)representatives.If you want to play around with this more, there is an excellent
article about this on Cut The
Knot complete with
history, equations, and fun applets.
下面是一个可以非常简单地解决这个问题的算法：
从每组分配 0 个伴侣开始。如果任何组中没有学生，则丢弃该组，因为不会为该组分配任何监护人。
如果分配的伴侣的总数等于 k，那么我们就完成了。
将一名监护人分配给一组。接受监护人的群体是每名学生监护人比例最低的群体。如果出现平局，请从监护人/学生比例最低的组中选择学生最多的组。如果仍然平局，则从所选组中选择按字母顺序排列在第一个的组。
转到步骤 2。
它会进行明确的确定性分配。这些比例将在值允许的范围内几乎相等。增加 k 不会减少对任何组的分配，因为它实际上只会导致发生额外的迭代，并且没有迭代会减少任何组的分配。
两个相同大小的组可能具有不同数量的伴侣，但是如果不重述问题以允许对 k 进行修改，则无法纠正此问题。在任何情况下，两个相同大小的组在分配上的差异都不会超过 1。
另一个答案中用于将表示分配给状态的所有算法都不必要地复杂，并且旨在最大限度地减少执行的计算步骤数（通过执行数值计算而不是增量分配）。我给出的算法在计算机上运行时非常简单。
Here is an algorithm that will solve the question very simply:
Begin with an apportionment of 0 chaperons per group. If any groups have no students in them, then throw out that group, as no chaperon will be assigned to such a group.
If the total number of assigned chaperons is equal to k, then we are done.
Assign one chaperon to one group. The group that is to receive the chaperon is the one with the lowest chaperons per student ratio. In the case of a tie, select the group with the most students among those with the lowest chaperons per student ratio. If there is still a tie, then from among those selected, choose the group that is alphabetically the first.
Go to step 2.
It makes unambiguous deterministic assignments. The proportions will be as nearly equal as the values allow. Increasing k will not decrease the assignments to any group, since it effectively just causes an additional iteration to occur and no iterations decrease any group's assignments.
It is possible for two groups of the same size to have a different number of chaperons, but this cannot be corrected without restating the problem to allow modifications to k. In no case will two groups of the same size differ in their assignments by more than 1.
All of the algorithms in the other answer for assigning representation to states are needlessly complicated, and are designed to minimize the number of computational steps performed (by doing numerical calculations rather than incremental assignments). The algorithm that I have given is very simple when run on a computer.