整数除以浮点数得到比例整数

Question

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

我有任意数量的花车：

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

和一个整数：

I 其中 I > 0.

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

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

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

如果：f1 = 0.4, f2 = 0.3, f3 = 0.3, I = 1 那么我需要 f1-result = 1 , f2-结果 = 0, f3-结果 = 0,
如果：f1 = 0.4, f2 = 0.4, f3 = 0.2, I = 1 那么我需要 f1-result = 1 , f2-result = 0, f3-result = 0 or f1-result = 0, f2-result = 1, f3-result = 0
如果：f1 = 0.6, f2 = 0.25, f3 = 0.15, I = 5 那么我需要 f1-result = 3 , f2-result = 2, f3-result = 1。

Answer 1

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

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

所以，通过"objects"一一分发。要找出哪个桶得到它，您需要找到低于其所需数量的最大差值的桶（如果有多个桶同样低于其所需水平，则只需选择第一个).这是 "unhappiest" 桶。

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

例如，让我们开始根据上述算法将对象分配到三个桶（分别需要 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% 基于未定义的除零性质的计算）。但是，这是确保初始分配给想要最高百分比的存储桶的好方法，之后百分比就会明确定义。

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

而且，如果您想要一些代码，您可以尝试查看它的实际效果（让我们面对现实吧，谁不会想要它？），请参阅以下内容 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]%)

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

Answer 2

投资者j应该至少获得floor(fj*I)股。要分配多余的份额，首先确定它们的数量 (x = I - sum(floor(fj*I) for all j))，然后 select 分数数组的第 x 个最大元素 fj*I - floor(fj*I)。每个分数大于这个的人都得到一份；刚好达到这个分数的人会根据需要得到 1 或 0，以使总数有效。

运行时间为O(n)，其中n为投资者人数

Answer 3

你用 f1+f2+....+fn=1 开始了这个问题，但你最后只提到了三个浮点数。解决这个问题的简单方法是将最小的 fi 乘以十的幂 (10^p) 以获得整数值。您从整数 (10^p) 中减去要分配的金额，以计算出您必须从每个浮点数中取回多少才能达到分配的金额，假设您带来了高达 (10^p) 的额外金额作为每个人都有自己的分享时间 (10^p)。您通过重复方案执行此操作，首先您从每个浮动中收回超过分配金额的金额。在下一次迭代中，您从按升序排序的每个浮点数中收集一个单位，但您应该考虑不要变为负数。测试你是否在每次扣除后都拿回了全部金额。

所以举例说明 f1=0.6，f2=0.25，f3=015，I=5。用 f(i,j) 声明一个浮点矩阵 f，其中 i=3 和 j=2 它是一个两列三行的矩阵。将浮点数存储在第一列中并按升序对矩阵进行排序。访问矩阵 f(1,1) 的第一个元素，我们得到 0.15。将其转换为整数，如 It = f(1,1)* (10^(number of decimals(f(1,1)))，我们得到 It=0.15*(10^2)。即 It=15。填充带有整数的矩阵第二列

f(1,2)=15
f(2,2)=25
f(3,2)=60

现在我要取回10^2-5=95的金额。设置它=95。第一轮，拥有超过 5 个的每个人都会退还多余的部分。所以我得到以下内容（为了简化示例，我跳过了 f(i,2) > 5 )

的测试

10 = f(1,2)-5; f(1,2)=f(1,2)-10
20 = f(2,2)-5; f(2,2)=f(2,2)-20 
55 = f(3,2)-5; f(3,2)=f(3,2)-55

直到知道我收回了 10+20+55=85。我得再去买一个十个。现在每个人都有五个。这是在三个迭代中完成的。循环的第一秒和第三运行将从每个 is 9 units 中得到一个 unit 。 现在我回来了 94 我还需要 一个单位 回来，这将 从 f(2,1 ) 当我达到 95 个单位时，循环将退出。经过三次迭代和第四次迭代的一步后，我的最终矩阵是

  f(1,2)=1, 
  f(2,2)=2, 
  f(2,3)=2.

由于显而易见的原因，总计为 5 迭代算法很简单。它迭代 f(i,2)。它测试如果 f(i,s)>0，那么它从 f(i,2) 中减去一个单位；将这一单位添加到到目前为止要求退回的金额中，并测试该金额是否等于要退回的总金额。如果为真，它会打破循环。

整数除以浮点数得到比例整数

Dividing integers by floats resulting in proportional integers

algorithm

integer

division

integer-division