处理分配问题的算法

我需要一种算法、技术或任何指导来优化以下问题：

我有两家公司：

• A公司有员工324人
• B公司有员工190人

员工总数（A+B）是514。我需要随机选择28%这 514 名员工中。

好的，那么我们就这样做吧：514 的 28% 是 143.92；哦...这很糟糕，我们在这里与人打交道，所以我们不能有小数位。好的，那么我会尝试向上或向下舍入。

如果我向下舍入：143 是 27,82101167%，这不好，因为我必须有至少 28%，所以我必须四舍五入为 144。

所以现在我知道必须选择144名员工。

现在主要问题来了...是时候检查每个公司必须使用多少百分比才能获得总数 144。我该如何做才能使每个公司的百分比尽可能接近 28%？

我来举例说明：

如果我只为每家公司申请 28%，我会得到：

• A 公司有 324 名雇主：0.28 * 324 = 90.72
• B 公司有 190 名雇主：0.28 * 190 = 53.2

再次，我以小数点结束。所以我必须弄清楚哪些应该向上舍入，哪些应该向下舍入以获得总共 144。

Note:在这个例子中我只使用了两家公司，但在实际问题中我有 30 家公司。

有很多方法 http://www.ctl.ua.edu/math103/apportionment/appmeth.htm进行分配，没有目标最好的方法 http://www.ams.org/samplings/feature-column/fcarc-apportionii2.

以下是州和席位，而不是公司和个人。信用可能归功于拉里鲍文博士，他在第一个链接的基本网站上被引用。

汉密尔顿法
也称为最大余数法，有时也称为文顿法。

程序：

1. 计算标准除数。
2. 计算每个州的标准配额。
3. 最初为每个州分配其较低配额。
4. 如果有多余席位，请按照标准配额小数部分的降序顺序将它们一次一个地分配给各州。

在这里，标准除数可以通过将总人口（每个公司的人口总和）除以您想要抽样的人数（在本例中为 144 人）来找到。标准配额是公司人口除以标准除数。下限配额是该值向下舍入。然而，这种方法有一些缺陷。

问题：

• 阿拉巴马悖论
  分配席位总数的增加会导致一个州失去一个席位。
• 人口悖论
  一个州人口的增加可能会导致该州失去一个席位。
• 新州悖论
  添加一个拥有公平份额席位的新州可能会影响其他州的席位数量。

这可能是最简单的实施方法。以下是一些其他方法及其相应的实现和缺点。

杰斐逊的方法
也称为最大除数法，在欧洲称为 d'Hondt 法或 Hagenbach-Bischoff 法。

程序：

1. 计算标准除数。
2. 计算每个州的标准配额。
3. 最初为每个州分配其较低配额。
4. Check to see if the sum of the Lower Quotas is equal to the correct number of seats to be apportioned.
   • 如果较低配额的总和等于要分配的正确席位数，则向每个州分配等于其较低配额的席位数。
   • 如果较低配额的总和不等于要分配的正确席位数，则通过反复试验找到一个数字，MD，称为修改除数来代替标准除数，以便当修改配额时，MQ，对于每个州（通过将每个州的人口除以 MD 而不是 SD 来计算）进行向下舍入，所有四舍五入（向下）修改配额的总和就是要分配的确切席位数。 （注意：MD 始终小于标准除数。）这些四舍五入（向下）的修改配额有时称为修改较低配额。分配每个州的修改后的较低配额。

Problem:

• 违反配额规则。 （但是，它只能违反上限配额，而不能违反下限配额。）

韦氏方法
也称为韦伯斯特-威尔科克斯法以及大分数法。

程序：

1. 计算标准除数。
2. 计算每个州的标准配额。
3. 如果某个州的标准配额的小数部分小于 0.5，则最初为其分配下限配额。
   如果某个州的标准配额的小数部分大于或等于 0.5，则最初为其分配上限配额。
   [换句话说，根据算术平均值（平均值）向下或向上舍入。]
4. Check to see if the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned.
   • 如果配额之和（步骤 3 中的下限和/或上限）等于要分配的正确席位数，则向每个州分配等于其配额（步骤 3 中的下限或上限）的席位数。
   • 如果配额总和（步骤 3 中的下限和/或上限）不等于要分配的正确席位数，则通过反复试验，找到一个数字 MD，称为修正除数以供使用的标准除数，以便当每个州的修改配额 MQ（通过将每个州的人口除以 MD 而不是 SD 来计算）基于算术平均值（平均值）进行舍入时，所有舍入的修改配额的总和是需要分配的确切席位数。分配每个州的修改后的舍入配额。

Problem:

• 违反配额规则。 （但是，违规行为很少见，并且通常与人为的情况有关。）

亨廷顿希尔法
也称为等比例法。

• 目前用于分配美国众议院的方法
• 由人口普查局首席统计师 Joseph A. Hill 和哈佛大学力学与数学教授 Edward V. Huntington 于 1911 年左右开发
• 初步术语：几何平均数

程序：

1. 计算标准除数。
2. 计算每个州的标准配额。
3. 如果某个州的标准配额的小数部分小于标准配额紧邻的两个整数的几何平均值（例如，16.47 紧邻 16 和 17），则最初为该州分配其下配额。
   如果某个州的标准配额的小数部分大于或等于标准配额紧邻的两个整数的几何平均值（例如，16.47 紧邻 16 和 17），则最初为该州分配上限配额。
   [换句话说，根据几何平均值向下或向上舍入。]
4. Check to see if the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned.
   • 如果配额之和（步骤 3 中的下限和/或上限）等于要分配的正确席位数，则向每个州分配等于其配额（步骤 3 中的下限或上限）的席位数。
   • 如果配额总和（步骤 3 中的下限和/或上限）不等于要分配的正确席位数，则通过反复试验，找到一个数字 MD，称为修正除数以供使用的标准除数，以便当每个州的修改配额 MQ（通过将每个州的人口除以 MD 而不是 SD 来计算）基于几何平均值进行舍入时，所有舍入的修改配额的总和就是准确的数量待分配的席位。分配每个州的修改后的舍入配额。

Problem:

• 违反配额规则。

作为参考，配额规则：

配额规则

始终仅分配下限和/或上限的分配方法遵循配额规则。