处理分配问题的算法

3
我需要一种算法、技术或任何指导来优化以下问题:
我有两个公司:
- 公司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个公司。

2
如果你需要随机选择144名员工,为什么要关心这些人来自哪家公司呢? - undefined
@PhamTrung 原因对于问题来说并不重要,我只是这样做。 - undefined
4个回答

3

许多方法可以进行配额分配,没有客观的最佳方法

以下是关于州和席位而不是公司和人的术语。功劳可能归功于被引用在第一个链接基础网站上的Larry Bowen博士。

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

步骤:

  1. 计算标准除数。
  2. 计算每个州的标准配额。
  3. 最初将每个州分配其下限配额。
  4. 如果有剩余席位,按其标准配额的小数部分降序逐个将其分配给各州。

在此,标准除数可以通过将总人口(每家公司人口的总和)除以要抽样的人数(本例中为144)来找到。标准配额是公司人口除以标准除数得出的值。下限配额是将此值向下取整。然而,这种方法有一些缺陷。

问题:

  • 阿拉巴马悖论
    席位总数增加导致某个州失去席位。
  • 人口悖论
    某个州人口的增加可能导致其失去席位。
  • 新州悖论
    添加一个具有其公平份额的新州可能会影响到其他州应得的席位数。

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

杰斐逊法 也称最大除数法,欧洲称为d'Hondt方法或Hagenbach-Bischoff方法。
程序: 1. 计算标准除数。 2. 计算每个州的标准配额。 3. 最初分配每个州的下限配额。 4. 检查下限配额之和是否等于要分配的正确席位数。
- 如果下限配额之和等于要分配的正确席位数,则将每个州分配与其下限配额相等的席位数。 - 如果下限配额之和不等于要分配的正确席位数,则通过试验和错误找到一个数字MD(称为修改除数),用MD代替标准除数,使得当对每个州的人口进行MD而不是SD的计算时,每个州的修改配额MQ向下取整后的总和等于要分配的确切席位数。(注意:MD始终小于标准除数。)这些向下取整的修改下限配额有时被称为修改下限配额。将每个州分配其修改下限配额。
问题: 违反配额规则。(但它只能违反上限配额,永远不会违反下限配额。)

韦伯斯特方法
也被称为韦伯斯特-威尔科克斯方法和主分数法。

步骤:

  1. 计算标准除数。
  2. 计算每个州的标准配额。
  3. 如果某个州的标准配额的小数部分小于0.5,则最初将其分配为下限配额。如果某个州的标准配额的小数部分大于或等于0.5,则最初将其分配为上限配额。[换句话说,根据算术平均值(平均数)四舍五入。]
  4. 检查配额(第3步的下限和/或上限配额)之和是否等于应分配的正确席位数。
    • 如果配额之和(第3步的下限和/或上限配额)等于应分配的正确席位数,则向每个州分配与其配额相等的席位数(来自第3步的下限或上限配额)。
    • 如果配额之和(第3步的下限和/或上限配额)不等于应分配的正确席位数,则通过试验和错误找到一个数字MD,称为修改除数,以代替标准除数,使得当每个州的修改配额MQ(通过将每个州的人口除以MD而不是SD计算)四舍五入后,所有四舍五入的修改配额之和等于应分配的确切席位数。将每个州分配其修改后的四舍五入配额。

问题:

  • 违反配额规则。(但是,违规情况很少,通常与人为制造的情况有关。)
亨廷顿-希尔(Huntington-Hill)方法,也称为等比例分配法。这是目前用于分配美国众议院席位的方法,由人口普查局首席统计员约瑟夫·希尔(Joseph A. Hill)和哈佛大学力学与数学教授爱德华·V·亨廷顿(Edward V. Huntington)于1911年左右开发。以下是该方法的步骤:
1. 计算标准除数。 2. 计算每个州的标准配额。 3. 如果一个州的标准配额的小数部分小于其所在两个整数的几何平均数(例如,16.47介于16和17之间),则最初将该州分配到其下限配额;如果一个州的标准配额的小数部分大于或等于其所在两个整数的几何平均数,则最初将该州分配到其上限配额。[换句话说,根据几何平均数向下或向上四舍五入。] 4. 检查配额总和(来自步骤3的下限和/或上限)是否等于应分配的正确席位数。
- 如果配额总和(来自步骤3的下限和/或上限)等于应分配的正确席位数,则向每个州分配与其配额相等的席位数(来自步骤3的下限或上限)。 - 如果配额总和(来自步骤3的下限和/或上限)不等于应分配的正确席位数,则通过试错找到一个称为修改除数(MD)的数字,该数字用于代替标准除数(SD),以便当每个州的修改配额(MQ)(通过将每个州的人口除以MD而不是SD计算)根据几何平均数四舍五入时,所有四舍五入后的修改配额之和等于应分配的确切席位数。向每个州分配其修改后的四舍五入配额。
问题:违反了配额规则。
参考配额规则:
配额规则:始终只分配下限和/或上限的分配方法遵循配额规则。

1
这将是一个很好的回答,如果你至少列举出许多方法,这样就可以在链接失效时进行搜索。如果你能为每个方法包括至少一行摘要,那就更好了。 - undefined
知道这个问题属于“分摊问题”类别非常有帮助。在我的情况下,我通过找到每个公司的较低配额来解决了这个问题,然后我随机选择n次(其中n是144减去所有较低配额的总和),选择一个公司(低于28%)将其较低配额增加一次。感谢您的答案! - undefined

2
该问题可以被描述为找到一组比率的最接近的整数近似值。例如,如果你想分别从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 - 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。
很可能这种问题描述方式在结果方面相当于先前回复中引用的某个算法。

我所描述的方法在整数平移下是不变的。因此,它归结为分配比率的小数部分,而不管比率的整数部分是什么。最小二乘解将是按分数大小递减顺序逐个四舍五入到达所需总数。这就是汉密尔顿方法。因此,汉密尔顿方法实现了整数比率估计的最小二乘解。阿拉巴马悖论适用于它。 - undefined

1
自从我最初发布这个问题以来,我在Martin Fowler的书《企业应用架构模式》(第489页和490页)中找到了对这个问题的准确描述。
Martin谈到了一个“Matt Foemmel的简单难题”,即将5美分分配给两个账户,但必须遵守70%和30%的分配。这更简单地描述了我的问题。
以下是他在书中提出的解决方案:
也许最常见的方法是忽略它——毕竟只有一两分钱。但这往往会让会计师感到不安。在分配时,您总是通过从迄今为止已分配的金额中减去来进行最后一次分配。这样可以避免丢失零头,但最后一次分配可能会累积一定数量的零头。允许Money类的用户在调用该方法时声明舍入方案。这允许程序员说70%的情况向上舍入,30%的情况向下舍入。如果您要在十个账户而不是两个账户之间进行分配,事情可能会变得复杂。您还必须记得四舍五入。为了鼓励人们记住,我看到一些Money类将舍入参数强制加入乘法操作中。这不仅会强迫程序员考虑她需要哪种舍入方式,还可能提醒她编写测试。然而,如果您有很多相同舍入方式的税收计算,情况会变得混乱。我最喜欢的解决方案:在货币上有一个分配函数。分配器的参数是一个数字列表,表示要分配的比例(它看起来像aMoney.allocate([7,3]))。分配器返回一个货币列表,保证不会丢失零头,通过在分配的货币上散布它们的方式,从外部看起来是伪随机的。分配器有缺陷:您必须记得使用它,并且任何关于零头去向的精确规则都很难执行。

附注:我只是希望有一个更好的名字来描述这种问题。分配似乎太具体和复杂了,而马特·福梅尔的简单难题则显得过于宽泛和冗长。也许有人可以想出一个更好的名字? - undefined

1
我的建议是只取每家公司的28%并向上取整到最接近的人数。
在您的情况下,您将选择91和54。不可否认,这确实会导致超过28%的一点点。
最准确的方法如下:
  • 计算您想要的确切数字。
  • 对于每个公司,取28%并向下取整。
  • 按余数降序排序公司。
  • 浏览列表并选择前n个元素,直到您得到所需的确切数字。

我对你的解决方案理解得不太好。你所说的"remainder"是什么意思?剩下的是什么?而你所说的"choose the top elements"又是什么意思?这样做怎么会得到144呢? - undefined
@PedroPinheiro . . . 余数是舍入值与28%之间的小数部分。 - undefined
这被称为汉密尔顿方法,可能是最容易实施的分配方法,但并不完美。例如,增加公司的人口可能会导致在某些情况下对其进行较少的抽样。 - undefined

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接