处理分配问题的算法

Question

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

我有两家公司:

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

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

好的，让我们开始吧: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 个总数。

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

Answer 1

有many methods执行分配，没有目标best method .

以下是州和席位方面的，而不是公司和人员方面的。第一个链接可能归功于 Larry Bowen 博士，他在基础站点上被引用。

Hamilton’s Method
Also known as the Method of Largest Remainders and sometimes as Vinton's Method.

Procedure:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. Initially assign each state its Lower Quota.
4. 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:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. Initially assign each state its Lower Quota.
4. 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:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. 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).]
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.
   • 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:

1. Calculate the Standard Divisor.
2. Calculate each state’s Standard Quota.
3. 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.]
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.
   • 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.