我有一组非负值。我想构建一个总和为 20 的值数组，以便它们与第一个数组成比例。
这将是一个简单的问题，除了我希望比例数组的总和正好为 20，以补偿任何舍入误差。
例如，数组
input = [400, 400, 0, 0, 100, 50, 50]
会产生
output = [8, 8, 0, 0, 2, 1, 1]
sum(output) = 20
然而，大多数情况下会有很多舍入误差，比如
input = [3, 3, 3, 3, 3, 3, 18]
天真地屈服
output = [1, 1, 1, 1, 1, 1, 10]
sum(output) = 16 (ouch)
有没有一种分配输出数组的好方法，以便每次加起来最多为 20？
您的问题类似于比例代表制，您希望在各方之间按比例分享 N 个席位（在您的情况下为 20），在您的情况下 [3, 3, 3, 3, 3, 3, 18]
不同国家使用了几种方法来处理舍入问题。我下面的代码使用了瑞士使用的Hagenbach-Bischoff 配额方法，该方法基本上将整数除以 (N+1) 后剩余的席位分配给余数最高的政党：
def proportional(nseats,votes):
"""assign n seats proportionaly to votes using Hagenbach-Bischoff quota
:param nseats: int number of seats to assign
:param votes: iterable of int or float weighting each party
:result: list of ints seats allocated to each party
"""
quota=sum(votes)/(1.+nseats) #force float
frac=[vote/quota for vote in votes]
res=[int(f) for f in frac]
n=nseats-sum(res) #number of seats remaining to allocate
if n==0: return res #done
if n<0: return [min(x,nseats) for x in res] # see siamii's comment
#give the remaining seats to the n parties with the largest remainder
remainders=[ai-bi for ai,bi in zip(frac,res)]
limit=sorted(remainders,reverse=True)[n-1]
#n parties with remainter larger than limit get an extra seat
for i,r in enumerate(remainders):
if r>=limit:
res[i]+=1
n-=1 # attempt to handle perfect equality
if n==0: return res #done
raise #should never happen
但是，这种方法并不总是为完全平等的政党提供与您的情况相同数量的席位：
proportional(20,[3, 3, 3, 3, 3, 3, 18])
[2,2,2,2,1,1,10]
这个问题有一个非常简单的答案：我已经做过很多次了。每次分配到新数组后，您将减少正在使用的值，如下所示：
而已！易于在任何编程语言或电子表格中实现。
该解决方案是最佳的，因为结果数组的元素与其理想的非舍入值的距离永远不会超过 1。让我们用您的示例进行演示：
T = 36，S = 20。B[1] = round(A[1] / T * S) = 2。（理想情况下，1.666 ....）
T = 33，S = 18。 B[2] = round(A[2] / T * S) = 2。（理想情况下，1.666....）
T = 30，S = 16。B[3] = round(A[3] / T * S) = 2. (理想情况下，1.666....)
T = 27, S = 14. B[4] = round(A[4] / T * S) = 2. (理想情况下，1.666....)
T = 24, S = 12. B[5] = round(A[5] / T * S) = 2. (理想情况下, 1.666....)
T = 21, S = 10. B[6] = round (A[6] / T * S) = 1。（理想情况下，1.666....）
T = 18，S = 9。B[7] = round(A[7] / T * S) = 9。（理想情况下，10）
请注意，将 B 中的每个值与括号中的理想值进行比较，差异永远不会超过 1。
有趣的是，重新排列数组中的元素可能会导致结果数组中出现不同的对应值。我发现按升序排列元素是最好的，因为它会导致实际和理想之间的平均百分比差异最小。
您设置了 3 个不兼容的要求。[1,1,1]不能使与成比例的整数值数组总和恰好为 20。您必须选择打破“总和恰好为 20”、“与输入成比例”和“整数值”要求之一。
如果您选择打破对整数值的要求，请使用浮点数或有理数。如果您选择打破确切的总和要求，那么您已经解决了问题。选择打破比例有点棘手。您可能采取的一种方法是确定总和的距离，然后通过输出数组随机分配更正。例如，如果您的输入是：
[1, 1, 1]
那么你可以先让它尽可能地求和，同时仍然是成比例的：
[7, 7, 7]
并且因为20 - (7+7+7) = -1，随机选择一个元素递减：
[7, 6, 7]
如果错误是4，您将选择四个元素来增加。
一个表现不佳但会提供正确结果的天真的解决方案......
编写一个迭代器，给定一个包含八个整数 ( candidate) 的数组和input数组，输出最远离与其他元素成比例的元素的索引（伪代码）：
function next_index(candidate, input)
// Calculate weights
for i in 1 .. 8
w[i] = candidate[i] / input[i]
end for
// find the smallest weight
min = 0
min_index = 0
for i in 1 .. 8
if w[i] < min then
min = w[i]
min_index = i
end if
end for
return min_index
end function
然后就这样做
result = [0, 0, 0, 0, 0, 0, 0, 0]
result[next_index(result, input)]++ for 1 .. 20
如果没有最佳解决方案，它将偏向数组的开头。
使用上面的方法，您可以通过向下舍入来减少迭代次数（就像您在示例中所做的那样），然后只需使用上面的方法添加由于舍入错误而遗漏的内容：
result = <<approach using rounding down>>
while sum(result) < 20
result[next_index(result, input)]++
所以上面的答案和评论很有帮助......尤其是来自@Frederik 的递减总和评论。
我提出的解决方案利用了这样一个事实，即对于输入数组 v，sum(v_i * 20) 可以被 sum(v) 整除。因此，对于 v 中的每个值，我乘以 20 并除以总和。我保留商，并累积余数。每当累加器大于 sum(v) 时，我将值加一。这样我就可以保证所有的余数都被纳入结果中。
那是清晰的吗？这是Python中的实现：
def proportion(values, total):
# set up by getting the sum of the values and starting
# with an empty result list and accumulator
sum_values = sum(values)
new_values = []
acc = 0
for v in values:
# for each value, find quotient and remainder
q, r = divmod(v * total, sum_values)
if acc + r < sum_values:
# if the accumlator plus remainder is too small, just add and move on
acc += r
else:
# we've accumulated enough to go over sum(values), so add 1 to result
if acc > r:
# add to previous
new_values[-1] += 1
else:
# add to current
q += 1
acc -= sum_values - r
# save the new value
new_values.append(q)
# accumulator is guaranteed to be zero at the end
print new_values, sum_values, acc
return new_values
（我添加了一个增强功能，如果累加器 > 余数，我会增加前一个值而不是当前值）