处理分配问题的算法
Algorithms to deal with apportionment problems
我需要一种算法、技术或任何指导来优化以下问题：
我有两家公司：
- A公司有324名员工
- B公司有190名员工
员工总数（A+B）是514，我需要随机抽取这514名员工中的select28%
好的，那我们来算吧：514的28%是143.92；哦……这样不好，我们这里是跟人打交道，不能有小数位。好的，我会尝试向上或向下舍入。
如果我四舍五入：143 是 27,82101167%，这不好，因为我必须 至少 28%，所以我必须四舍五入到 144。
所以现在我知道 144 名员工必须 selected。
现在主要问题来了...是时候检查我必须为每个公司使用多少百分比才能获得总数 144。我该怎么做才能使百分比尽可能接近 28每个公司的百分比？
我来举例说明：
如果我只为每家公司申请 28%，我将获得：
- 公司A有324个雇主：0.28 * 324 = 90.72
- 公司B有190个雇主：0.28 * 190 = 53.2
同样，我以小数位结尾。所以我必须弄清楚哪些应该四舍五入，哪些应该四舍五入才能得到 144 个。
注意：这个例子我只用了两家公司，但在实际问题中我有30家公司。
我的建议是只取每家公司的 28%，然后四舍五入到最接近的人。
在你的情况下，你会选择 91 和 54。诚然，这确实会导致超过 28%。
最准确的方法如下：
- 计算出您想要的确切数字。
- 每家公司取 28% 并四舍五入向下。
- 按余数对公司进行降序排序。
- 遍历列表并选择前 n 个元素，直到得到您想要的数字。
有many methods to perform apportionment, and no objective best method.
以下是州和席位，而不是公司和人。可能要归功于 Larry Bowen 博士，他在基础站点上首次被引用 link。
Hamilton’s Method
Also known as the Method of Largest Remainders and sometimes as Vinton's Method.
Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign each state its Lower Quota.
- If there are surplus seats, give them, one at a time, to states in descending order of the fractional parts of their Standard Quota.
在这里，标准除数可以通过将总人口（每个公司的人口总和）除以您要抽样的人数（在本例中为 144）来找到。标准配额是公司人口除以标准除数。 Lower Quota 是向下舍入的值。但是，这种方法也有一些缺陷。
Problems:
- The Alabama Paradox
An increase in the total number of seats to be apportioned causes a state to lose a seat.
- The Population Paradox
An increase in a state’s population can cause it to lose a seat.
- The New States Paradox
Adding a new state with its fair share of seats can affect the number of seats due other states.
这可能是最简单的实现方法。下面是一些其他方法及其伴随的实现和缺点。
Jefferson’s Method
Also known as the Method of Greatest Divisors and in Europe as the Method of d'Hondt or the Hagenbach-Bischoff Method.
Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign each state its Lower Quota.
- Check to see if the sum of the Lower Quotas is equal to the correct number of seats to be apportioned.
- If the sum of the Lower Quotas is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Lower Quota.
- If the sum of the Lower Quotas is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded DOWN, the sum of all the rounded (down) Modified Quotas is the exact number of seats to be apportioned. (Note: The MD will always be smaller than the Standard Divisor.) These rounded (down) Modified Quotas are sometimes called Modified Lower Quotas. Apportion each state its Modified Lower Quota.
Problem:
- Violates the Quota Rule. (However, it can only violate Upper Quota—never Lower Quota.)
Webster’s Method
Also known as the Webster-Willcox Method as well as the Method of Major Fractions.
Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign a state its Lower Quota if the fractional part of its Standard Quota is less than 0.5.
Initially assign a state its Upper Quota if the fractional part of its Standard Quota is greater than or equal to 0.5.
[In other words, round down or up based on the arithmetic mean (average).]
- 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.
- If the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Quota (Lower or Upper from Step 3).
- If the sum of the Quotas (Lower and/or Upper from Step 3) is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded based on the arithmetic mean (average) , the sum of all the rounded Modified Quotas is the exact number of seats to be apportioned. Apportion each state its Modified Rounded Quota.
Problem:
- Violates the Quota Rule. (However, violations are rare and are usually associated with contrived situations.)
Huntington-Hill Method
Also known as the Method of Equal Proportions.
- Current method used to apportion U.S. House
- Developed around 1911 by Joseph A. Hill, Chief Statistician of the Bureau of the Census and Edward V. Huntington, Professor of Mechanics & Mathematics, Harvard
- Preliminary terminology: The Geometric Mean
Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign a state its Lower Quota if the fractional part of its Standard Quota is less than the Geometric Mean of the two whole numbers that the Standard Quota is immediately between (for example, 16.47 is immediately between 16 and 17).
Initially assign a state its Upper Quota if the fractional part of its Standard Quota is greater than or equal to the Geometric Mean of the two whole numbers that the Standard Quota is immediately between (for example, 16.47 is immediately between 16 and 17).
[In other words, round down or up based on the geometric mean.]
- 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.
- If the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Quota (Lower or Upper from Step 3).
- If the sum of the Quotas (Lower and/or Upper from Step 3) is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded based on the geometric mean, the sum of all the rounded Modified Quotas is the exact number of seats to be apportioned. Apportion each state its Modified Rounded Quota.
Problem:
- Violates the Quota Rule.
作为参考，配额规则：
Quota Rule
An apportionment method that always allocates only lower and/or upper bounds follows the quota rule.
自从我最初发布这个问题后，我在 Martin Fowler 的书 "Patterns of Enterprise Application Architecture"（第 489 和 490 页）中看到了对这个确切问题的描述。
Martin 谈到 "Matt Foemmel’s simple conundrum" 在两个帐户之间分配 5 美分，但必须遵守 70% 和 30% 的分配。这以更简单的方式描述了我的问题。
以下是他在书中针对该问题提出的解决方案：
- Perhaps the most common is to ignore it—after all, it’s only a penny here
and there. However this tends to make accountants understandably nervous.
- When allocating you always do the last allocation by subtracting from
what you’ve allocated so far. This avoids losing pennies, but you can get a
cumulative amount of pennies on the last allocation.
- Allow users of a Money class to declare the rounding scheme when they call
the method. This permits a programmer to say that the 70% case rounds up and
the 30% rounds down. Things can get complicated when you allocate across ten
accounts instead of two. You also have to remember to round. To encourage people to remember I’ve seen some Money classes force a rounding parameter into
the multiply operation. Not only does this force the programmer to think about
what rounding she needs, it also might remind her of the tests to write. However,
it gets messy if you have a lot of tax calculations that all round the same way.
- My favorite solution: have an allocator function on the money. The
parameter to the allocator is a list of numbers, representing the ratio to be allocated (it would look something like aMoney.allocate([7,3])). The allocator returns
a list of monies, guaranteeing that no pennies get dropped by scattering them
across the allocated monies in a way that looks pseudo-random from the outside. The allocator has faults: You have to remember to use it and any precise
rules about where the pennies go are difficult to enforce.
这个问题可以被定义为找到一组比率的最接近整数近似值的问题。例如，如果要分别分配来自 3 个组的 A、B、C ≥ 0 成员以匹配比率 a、b、c ≥ 0（a + b + c = N > 0），其中 N = A + B + C > 0 是所需的总分配，然后您将 (a, b, c) 近似为 (A, B, C)，其中 A、B 和 C 限制为整数。
解决这个问题的一种方法可能是将其设置为最小二乘问题 - 最小化 |a - A|² + |b - B|² + |c - C|²；受约束 A + B + C = N 且 A, B, C ≥ 0.
最优的必要条件是它是关于离散单元变化的局部最优。例如，(A,B,C) → (A+1,B-1,C)，如果 B > 0 ... 满足条件 (A - B ≥ a - b - 1 或 B = 0)。
对于手头的情况，优化问题是：
|A - a|² + |B - b|²
a = 144×324/(324+190) ≅ 90.770, b = 144×190/(324+190) ≅ 53.230
这导致条件：
A - B ≥ a - b - 1 ≅ +36.541 或 B = 0
B - A ≥ b - a - 1 ≅ -38.541 或 A = 0
A + B = 144
因为它们是整数，所以不等式可以加强：
A - B ≥ +37 或 B = 0
B - A ≥ -38 或 A = 0
A + B = 144
边界情况 A = 0 和 B = 0 被排除，因为它们不满足所有三个条件。所以，你剩下 37 ≤ A - B ≤ 38 或者，因为 A + B = 144：181 ≤ 2A ≤ 182 或 A = 91 ... 和 B = 53.
就其结果而言，这种构建问题的方式很有可能等同于先前回复中引用的算法之一。
我需要一种算法、技术或任何指导来优化以下问题：
我有两家公司：
- A公司有324名员工
- B公司有190名员工
员工总数（A+B）是514，我需要随机抽取这514名员工中的select28%
好的，那我们来算吧：514的28%是143.92；哦……这样不好，我们这里是跟人打交道，不能有小数位。好的，我会尝试向上或向下舍入。
如果我四舍五入：143 是 27,82101167%，这不好，因为我必须 至少 28%，所以我必须四舍五入到 144。
所以现在我知道 144 名员工必须 selected。
现在主要问题来了...是时候检查我必须为每个公司使用多少百分比才能获得总数 144。我该怎么做才能使百分比尽可能接近 28每个公司的百分比？
我来举例说明：
如果我只为每家公司申请 28%，我将获得：
- 公司A有324个雇主：0.28 * 324 = 90.72
- 公司B有190个雇主：0.28 * 190 = 53.2
同样，我以小数位结尾。所以我必须弄清楚哪些应该四舍五入，哪些应该四舍五入才能得到 144 个。
注意：这个例子我只用了两家公司，但在实际问题中我有30家公司。
我的建议是只取每家公司的 28%，然后四舍五入到最接近的人。
在你的情况下，你会选择 91 和 54。诚然，这确实会导致超过 28%。
最准确的方法如下：
- 计算出您想要的确切数字。
- 每家公司取 28% 并四舍五入向下。
- 按余数对公司进行降序排序。
- 遍历列表并选择前 n 个元素，直到得到您想要的数字。
有many methods to perform apportionment, and no objective best method.
以下是州和席位，而不是公司和人。可能要归功于 Larry Bowen 博士，他在基础站点上首次被引用 link。
Hamilton’s Method
Also known as the Method of Largest Remainders and sometimes as Vinton's Method.Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign each state its Lower Quota.
- If there are surplus seats, give them, one at a time, to states in descending order of the fractional parts of their Standard Quota.
在这里，标准除数可以通过将总人口（每个公司的人口总和）除以您要抽样的人数（在本例中为 144）来找到。标准配额是公司人口除以标准除数。 Lower Quota 是向下舍入的值。但是，这种方法也有一些缺陷。
Problems:
- The Alabama Paradox
An increase in the total number of seats to be apportioned causes a state to lose a seat.- The Population Paradox
An increase in a state’s population can cause it to lose a seat.- The New States Paradox
Adding a new state with its fair share of seats can affect the number of seats due other states.
这可能是最简单的实现方法。下面是一些其他方法及其伴随的实现和缺点。
Jefferson’s Method
Also known as the Method of Greatest Divisors and in Europe as the Method of d'Hondt or the Hagenbach-Bischoff Method.Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign each state its Lower Quota.
- Check to see if the sum of the Lower Quotas is equal to the correct number of seats to be apportioned.
- If the sum of the Lower Quotas is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Lower Quota.
- If the sum of the Lower Quotas is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded DOWN, the sum of all the rounded (down) Modified Quotas is the exact number of seats to be apportioned. (Note: The MD will always be smaller than the Standard Divisor.) These rounded (down) Modified Quotas are sometimes called Modified Lower Quotas. Apportion each state its Modified Lower Quota.
Problem:
- Violates the Quota Rule. (However, it can only violate Upper Quota—never Lower Quota.)
Webster’s Method
Also known as the Webster-Willcox Method as well as the Method of Major Fractions.Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign a state its Lower Quota if the fractional part of its Standard Quota is less than 0.5.
Initially assign a state its Upper Quota if the fractional part of its Standard Quota is greater than or equal to 0.5.
[In other words, round down or up based on the arithmetic mean (average).]- 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.
- If the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Quota (Lower or Upper from Step 3).
- If the sum of the Quotas (Lower and/or Upper from Step 3) is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded based on the arithmetic mean (average) , the sum of all the rounded Modified Quotas is the exact number of seats to be apportioned. Apportion each state its Modified Rounded Quota.
Problem:
- Violates the Quota Rule. (However, violations are rare and are usually associated with contrived situations.)
Huntington-Hill Method
Also known as the Method of Equal Proportions.
- Current method used to apportion U.S. House
- Developed around 1911 by Joseph A. Hill, Chief Statistician of the Bureau of the Census and Edward V. Huntington, Professor of Mechanics & Mathematics, Harvard
- Preliminary terminology: The Geometric Mean
Procedure:
- Calculate the Standard Divisor.
- Calculate each state’s Standard Quota.
- Initially assign a state its Lower Quota if the fractional part of its Standard Quota is less than the Geometric Mean of the two whole numbers that the Standard Quota is immediately between (for example, 16.47 is immediately between 16 and 17).
Initially assign a state its Upper Quota if the fractional part of its Standard Quota is greater than or equal to the Geometric Mean of the two whole numbers that the Standard Quota is immediately between (for example, 16.47 is immediately between 16 and 17).
[In other words, round down or up based on the geometric mean.]- 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.
- If the sum of the Quotas (Lower and/or Upper from Step 3) is equal to the correct number of seats to be apportioned, then apportion to each state the number of seats equal to its Quota (Lower or Upper from Step 3).
- If the sum of the Quotas (Lower and/or Upper from Step 3) is NOT equal to the correct number of seats to be apportioned, then, by trial and error, find a number, MD, called the Modified Divisor to use in place of the Standard Divisor so that when the Modified Quota, MQ, for each state (computed by dividing each State's Population by MD instead of SD) is rounded based on the geometric mean, the sum of all the rounded Modified Quotas is the exact number of seats to be apportioned. Apportion each state its Modified Rounded Quota.
Problem:
- Violates the Quota Rule.
作为参考，配额规则：
Quota Rule
An apportionment method that always allocates only lower and/or upper bounds follows the quota rule.
自从我最初发布这个问题后，我在 Martin Fowler 的书 "Patterns of Enterprise Application Architecture"（第 489 和 490 页）中看到了对这个确切问题的描述。
Martin 谈到 "Matt Foemmel’s simple conundrum" 在两个帐户之间分配 5 美分，但必须遵守 70% 和 30% 的分配。这以更简单的方式描述了我的问题。
以下是他在书中针对该问题提出的解决方案：
- Perhaps the most common is to ignore it—after all, it’s only a penny here and there. However this tends to make accountants understandably nervous.
- When allocating you always do the last allocation by subtracting from what you’ve allocated so far. This avoids losing pennies, but you can get a cumulative amount of pennies on the last allocation.
- Allow users of a Money class to declare the rounding scheme when they call the method. This permits a programmer to say that the 70% case rounds up and the 30% rounds down. Things can get complicated when you allocate across ten accounts instead of two. You also have to remember to round. To encourage people to remember I’ve seen some Money classes force a rounding parameter into the multiply operation. Not only does this force the programmer to think about what rounding she needs, it also might remind her of the tests to write. However, it gets messy if you have a lot of tax calculations that all round the same way.
- My favorite solution: have an allocator function on the money. The parameter to the allocator is a list of numbers, representing the ratio to be allocated (it would look something like aMoney.allocate([7,3])). The allocator returns a list of monies, guaranteeing that no pennies get dropped by scattering them across the allocated monies in a way that looks pseudo-random from the outside. The allocator has faults: You have to remember to use it and any precise rules about where the pennies go are difficult to enforce.
这个问题可以被定义为找到一组比率的最接近整数近似值的问题。例如，如果要分别分配来自 3 个组的 A、B、C ≥ 0 成员以匹配比率 a、b、c ≥ 0（a + b + c = N > 0），其中 N = A + B + C > 0 是所需的总分配，然后您将 (a, b, c) 近似为 (A, B, C)，其中 A、B 和 C 限制为整数。
解决这个问题的一种方法可能是将其设置为最小二乘问题 - 最小化 |a - A|² + |b - B|² + |c - C|²；受约束 A + B + C = N 且 A, B, C ≥ 0.
最优的必要条件是它是关于离散单元变化的局部最优。例如，(A,B,C) → (A+1,B-1,C)，如果 B > 0 ... 满足条件 (A - B ≥ a - b - 1 或 B = 0)。
对于手头的情况，优化问题是：
|A - a|² + |B - b|²
a = 144×324/(324+190) ≅ 90.770, b = 144×190/(324+190) ≅ 53.230
这导致条件：
A - B ≥ a - b - 1 ≅ +36.541 或 B = 0
B - A ≥ b - a - 1 ≅ -38.541 或 A = 0
A + B = 144
因为它们是整数，所以不等式可以加强：
A - B ≥ +37 或 B = 0
B - A ≥ -38 或 A = 0
A + B = 144
边界情况 A = 0 和 B = 0 被排除，因为它们不满足所有三个条件。所以，你剩下 37 ≤ A - B ≤ 38 或者，因为 A + B = 144：181 ≤ 2A ≤ 182 或 A = 91 ... 和 B = 53.
就其结果而言，这种构建问题的方式很有可能等同于先前回复中引用的算法之一。