如何分配整数列表，使其尽可能接近平衡? [英] How do you distribute a list of integers to be as close to balanced as possible?

问题描述

您如何平衡一组项目?通过平衡，这4个变量中的每个变量与其他任何变量的方差均不得大于+1.

How do you balance a set of items? By balance, each of the 4 variables should have no variance of more than +1 from any other variable.

每个数字必须保持完整，因为它们代表1个要转让的实物.

Each number must remain whole, as they represent 1 physical item to be transferred.

Input a=1, b=2, c=3, d=10 
Output a=4, b=4, c=4, d=4
Ouput:
    Move 3 from d to a
    Move 2 from d to b
    Move 1 from d to c

Input a=1, b=2, c=0, d=0
Ouput a=1, b=1, c=1, d=0
Output:
    Move 1 from b to c

Input a=1, b=0, c=0, d=0
Output a=1, b=0, c=0, d=0
Output:
    Move None

Input a=0, b=1, c=0, d=1
Output a=0, b=1, c=0, d=1
Output:
    Move None

推荐答案

否，它不是一组if/else语句.将您的值放入列表，而不是单独的变量.取均值，截断为整数.将其复制到另一个长度相同的列表中.您现在有类似的东西

No, it's not a set of if/else statements. Put your values into a list, not separate variables. Take the mean, truncated to an integer. Replicate that mean in another list of the same length. You now have something like

vals = [1, 3, 4, 10]
mean = [4, 4, 4, 4]

请注意，您还有2个项目.您需要分发这些. 在均值列表中，将1加到超出均值的任何元素上，直到用完剩余或元素.您现在有

Note that you have 2 items left over. You need to distribute those. In the mean list, add 1 to any element that's over the mean, until you run out of leftovers or elements. You now have

vals = [1, 3, 4, 10]
mean = [4, 4, 4, 5]

在这种情况下，您还剩下1个.将其添加到其他任何元素:

In this case, you still have 1 left over. Add it to any other element:

vals = [1, 3, 4, 10]
mean = [4, 5, 4, 5]

现在，比较列表(一次只比较一个元素)并报告所需的动作是很麻烦的.这样可以为您提供最少数量的已移动项目，以获得所需的分配.

Now, it's tribial to compare the lists, one element at a time, and report the moves needed. This gives you the minimal quantity of moved items to get the desired distribution.

这能让你前进吗?

回复OP评论

首先，您的过帐要求余额，而不是所需的一系列转帐.接下来，我看不到不是微不足道的地方.接收者小于均值"数组的任何内容；还有更多的是捐助者.您永远不会让产品移动超过一次:只需将转移限制在可用数量和所需数量中的较小者即可.

First of all, your posting asked for the balance, not the series of transfers needed. Next, I don't see where it isn't trivial. Anything less than the "mean" array is a recipient; anything more is a donor. You never have product moving more than once: just limit the transfer to the smaller of the amount available and the amount needed.

考虑一个简单但不平凡的情况:

Consider a simple, but non-trivial case:

vals = [1, 2, 10, 1, 6]
mean = [4, 4, 4, 4, 4]
diff = [-3, -2, 6, -3, 2]

您可以按任何顺序识别移动；为简单起见，我们将在两组中从右到左.是的，如果E给B多余的2钱，而C给A和D各自提供3钱，有一个简单的解决方案，但是这个问题并不需要最少的装运，而只是有效地运送了许多物品.

You can identify the moves in any order; for simplicity, we'll go right to left in both groups. Yes, there is an easy solution if E gives its 2 excess to B, while C supplies 3 each to A and D, but the problem doesn't call for fewest shipments, just efficient number of items moved.

A 有1个项目，但需要4个:从 C 中获取，第一个有多余元素的元素，有6个额外元素.

A has 1 item, but needs 4: take them from C, the first element with an excess, which has 6 extra.

vals = [4, 2, 7, 1, 6]
mean = [4, 4, 4, 4, 4]
diff = [0 -2, 3, -3, 2]

B 还需要2个项目，也可以从 C 获得:

B needs 2 more items, which it can also get from C:

vals = [4, 4, 5, 1, 6]
mean = [4, 4, 4, 4, 4]
diff = [0, 0, 1, -3, 2]

D 还需要3个，但是 C 仅剩一个:拿走.

D needs 3 more, but C has only one remaining: take it.

vals = [4, 4, 4, 2, 6]
mean = [4, 4, 4, 4, 4]
diff = [0, 0, 0, -2, 2]

...最后，最后一次传输现在很明显.

... and finally, the last transfer is now obvious.

那能让您再次移动吗?

这篇关于如何分配整数列表，使其尽可能接近平衡?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！