algorithm - 整数除以 float 得到比例整数

Question

最近我在做一个项目的时候遇到了一个很难解决的问题。我想问你们一个解决方案/算法来解决它，因为我真的很难想出一个聪明的主意来这样做。

我有任意数量的 float :

• f1, f2, ..., fn 其中 f1 + f2 + ... + fn = 1

和一个整数:

• I 其中 I > 0。

我需要将整数 I 分成 float ，就好像我在分配不可分割的东西一样。所以基本上这个比例必须在某种意义上保持不变，从某种意义上说，最大的 float 必须得到最大的整数。一个很好的比喻就好像我在分割不能分割的股票。

如果第一个投资者拥有 0.6% 的股票，第二个投资者拥有 0.4%，给定 1 只股票进行拆分，我会将其分配给第一个 (100% 0%)。如果有两只股票，我会给第一只股票一只，第二只股票一只(50% 50%)。请注意，我总是希望拆分尽可能成比例(尽可能接近 60% 40%)。

问题本身并没有明确定义，但是对于什么应该发生什么不应该发生有一定的认识。一些很容易在我脑海中浮现的例子是:

1. 如果:f1 = 0.4, f2 = 0.3, f3 = 0.3, I = 1 那么我需要f1-result = 1, f2-result = 0, f3-结果 = 0,

2. 如果:f1 = 0.4, f2 = 0.4, f3 = 0.2, I = 1 那么我需要f1-result = 1, f2-result = 0, f3-结果 = 0 或 f1-result = 0, f2-result = 1, f3-result = 0

3. 如果:f1 = 0.6, f2 = 0.25, f3 = 0.15, I = 5 那么我需要f1-result = 3, f2-result = 2, f3-结果 = 1。

Answer 1

这是我的处理方式，至少在最初是这样。

每个桶都有它需要的期望数量。这是基于它们的浮点值，所有浮点值总和为 1。

于是，把要分配的“对象”一一过一遍。要确定哪个桶得到它，您需要找到低于其所需数量的最大差异的桶(如果有多个桶同样低于其所需水平，则只需选择第一个)。这是“最不幸”的桶。

然后您将该对象分配到那个桶中，调整数字并移动到下一个对象。这意味着一个对象总是以这样一种方式分发，以使最不幸的桶的生活好一点(天哪，这听起来像我是一名社会 worker )。

例如，让我们开始根据上述算法将对象分配到三个桶(分别需要 50%、30% 和 20%)。

括号中的第二个数字是每个桶与其期望百分比的偏差因此，在每个阶段，我们选择最低于期望水平的桶，最不快乐的桶(由 * 表示) >):

BucketA (50%)  BucketB (30%)  BucketC (20%)
-------------  -------------  -------------
 0 (0%,-50*)    0 (0%,-30)     0 (0%,-20)
 1 (100%,+50)   0 (0%,-30*)    0 (0%,-20)
 1 (50%,+0)     1 (50%,+20)    0 (0%,-20*)
 1 (33%,-17*)   1 (33%,+3)     1 (33%,+13)
 2 (50%,+0)     1 (25%,-5*)    1 (25%,+5)
 2 (40%,-10*)   2 (40%,+10)    1 (20%,+0)
 3 (50%,+0)     2 (33%,+3)     1 (17%,-3*)
 3 (43%,-7*)    2 (29%,-1)     2 (29%,+9)
 4 (50%,+0)     2 (25%,-5*)    2 (25%,+5)
 4 (44%,-6*)    3 (33%,+3)     2 (22%,+2)
 5 (50%,+0)     3 (30%,+0)     2 (20%,+0)

请注意，初始条件的所有桶都在 0%，尽管这在技术上是不正确的(它可以很容易地被认为是 100% 或什至是 3.14159%，基于未定义的除零性质的计算)。但是，这是确保初始分配到想要最高百分比的存储桶的好方法，之后百分比将得到明确定义。

您可以从上面的表格中看出，对象的分布最终会导致预期的结果。

---

而且，如果您想要一些可以玩的代码以查看实际效果(让我们面对现实吧，谁不想要它？)，请参阅以下 Python 程序:

desiredPct = [50, 30, 20]
bucket = [0, 0, 0]
count = 0

# Allocate first item specially so no concern with div-by-zero.

idx = desiredPct.index(max(desiredPct))
happy_min = -desiredPct[idx]
bucket[idx] += 1
count += 1

actualPct = [x * 100 / count for x in bucket]
print "Unhappiest %6.2f @ %d, want %s%%, have %s (%s%%)" % (happy_min, idx, desiredPct, bucket, actualPct)

# Allocate all others in loop.

for i in range(99):
    # Get most disadvantaged bucket.

    idx = 0
    happy_min = bucket[idx] * 100 / sum(bucket) - desiredPct[idx]
    for j in range(1, len(bucket)):
        happy = bucket[j] * 100 / sum(bucket) - desiredPct[j]
        if happy < happy_min:
            idx = j
            happy_min = happy

    bucket[idx] += 1
    count += 1
    actualPct = [x * 100 / count for x in bucket]
    print "Unhappiest %6.2f @ %d, want %s%%, have %s (%s%%)" % (happy_min, idx, desiredPct, bucket, actualPct)

哪些输出:

Unhappiest -50.00 @ 0, want [50, 30, 20]%, have [1, 0, 0] ([100, 0, 0]%)
Unhappiest -30.00 @ 1, want [50, 30, 20]%, have [1, 1, 0] ([50, 50, 0]%)
Unhappiest -20.00 @ 2, want [50, 30, 20]%, have [1, 1, 1] ([33, 33, 33]%)
Unhappiest -17.00 @ 0, want [50, 30, 20]%, have [2, 1, 1] ([50, 25, 25]%)
Unhappiest  -5.00 @ 1, want [50, 30, 20]%, have [2, 2, 1] ([40, 40, 20]%)
Unhappiest -10.00 @ 0, want [50, 30, 20]%, have [3, 2, 1] ([50, 33, 16]%)
Unhappiest  -4.00 @ 2, want [50, 30, 20]%, have [3, 2, 2] ([42, 28, 28]%)
Unhappiest  -8.00 @ 0, want [50, 30, 20]%, have [4, 2, 2] ([50, 25, 25]%)
Unhappiest  -5.00 @ 1, want [50, 30, 20]%, have [4, 3, 2] ([44, 33, 22]%)
Unhappiest  -6.00 @ 0, want [50, 30, 20]%, have [5, 3, 2] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [6, 3, 2] ([54, 27, 18]%)
Unhappiest  -3.00 @ 1, want [50, 30, 20]%, have [6, 4, 2] ([50, 33, 16]%)
Unhappiest  -4.00 @ 2, want [50, 30, 20]%, have [6, 4, 3] ([46, 30, 23]%)
Unhappiest  -4.00 @ 0, want [50, 30, 20]%, have [7, 4, 3] ([50, 28, 21]%)
Unhappiest  -2.00 @ 1, want [50, 30, 20]%, have [7, 5, 3] ([46, 33, 20]%)
Unhappiest  -4.00 @ 0, want [50, 30, 20]%, have [8, 5, 3] ([50, 31, 18]%)
Unhappiest  -2.00 @ 2, want [50, 30, 20]%, have [8, 5, 4] ([47, 29, 23]%)
Unhappiest  -3.00 @ 0, want [50, 30, 20]%, have [9, 5, 4] ([50, 27, 22]%)
Unhappiest  -3.00 @ 1, want [50, 30, 20]%, have [9, 6, 4] ([47, 31, 21]%)
Unhappiest  -3.00 @ 0, want [50, 30, 20]%, have [10, 6, 4] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [11, 6, 4] ([52, 28, 19]%)
Unhappiest  -2.00 @ 1, want [50, 30, 20]%, have [11, 7, 4] ([50, 31, 18]%)
Unhappiest  -2.00 @ 2, want [50, 30, 20]%, have [11, 7, 5] ([47, 30, 21]%)
Unhappiest  -3.00 @ 0, want [50, 30, 20]%, have [12, 7, 5] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [12, 8, 5] ([48, 32, 20]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [13, 8, 5] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [13, 8, 6] ([48, 29, 22]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [14, 8, 6] ([50, 28, 21]%)
Unhappiest  -2.00 @ 1, want [50, 30, 20]%, have [14, 9, 6] ([48, 31, 20]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [15, 9, 6] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [16, 9, 6] ([51, 29, 19]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [16, 10, 6] ([50, 31, 18]%)
Unhappiest  -2.00 @ 2, want [50, 30, 20]%, have [16, 10, 7] ([48, 30, 21]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [17, 10, 7] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [17, 11, 7] ([48, 31, 20]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [18, 11, 7] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [18, 11, 8] ([48, 29, 21]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [19, 11, 8] ([50, 28, 21]%)
Unhappiest  -2.00 @ 1, want [50, 30, 20]%, have [19, 12, 8] ([48, 30, 20]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [20, 12, 8] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [21, 12, 8] ([51, 29, 19]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [21, 13, 8] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [21, 13, 9] ([48, 30, 20]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [22, 13, 9] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [22, 14, 9] ([48, 31, 20]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [23, 14, 9] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [23, 14, 10] ([48, 29, 21]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [24, 14, 10] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [24, 15, 10] ([48, 30, 20]%)
Unhappiest  -2.00 @ 0, want [50, 30, 20]%, have [25, 15, 10] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [26, 15, 10] ([50, 29, 19]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [26, 16, 10] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [26, 16, 11] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [27, 16, 11] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [27, 17, 11] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [28, 17, 11] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [28, 17, 12] ([49, 29, 21]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [29, 17, 12] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [29, 18, 12] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [30, 18, 12] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [31, 18, 12] ([50, 29, 19]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [31, 19, 12] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [31, 19, 13] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [32, 19, 13] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [32, 20, 13] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [33, 20, 13] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [33, 20, 14] ([49, 29, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [34, 20, 14] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [34, 21, 14] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [35, 21, 14] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [36, 21, 14] ([50, 29, 19]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [36, 22, 14] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [36, 22, 15] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [37, 22, 15] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [37, 23, 15] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [38, 23, 15] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [38, 23, 16] ([49, 29, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [39, 23, 16] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [39, 24, 16] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [40, 24, 16] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [41, 24, 16] ([50, 29, 19]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [41, 25, 16] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [41, 25, 17] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [42, 25, 17] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [42, 26, 17] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [43, 26, 17] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [43, 26, 18] ([49, 29, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [44, 26, 18] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [44, 27, 18] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [45, 27, 18] ([50, 30, 20]%)
Unhappiest   0.00 @ 0, want [50, 30, 20]%, have [46, 27, 18] ([50, 29, 19]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [46, 28, 18] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [46, 28, 19] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [47, 28, 19] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [47, 29, 19] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [48, 29, 19] ([50, 30, 19]%)
Unhappiest  -1.00 @ 2, want [50, 30, 20]%, have [48, 29, 20] ([49, 29, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [49, 29, 20] ([50, 29, 20]%)
Unhappiest  -1.00 @ 1, want [50, 30, 20]%, have [49, 30, 20] ([49, 30, 20]%)
Unhappiest  -1.00 @ 0, want [50, 30, 20]%, have [50, 30, 20] ([50, 30, 20]%)

这也表明，一旦您第一次获得了期望的结果，对象的分布往往会接近您想要的。