你如何分割的阵列分为两部分，使得所述两个部分具有相等的平均？ [英] How do you partition an array into 2 parts such that the two parts have equal average?

问题描述

你如何分割的阵列分为两部分，使得所述两个部分具有相等的平均？每个分区可能包含与非连续数组中的元素。 唯一的算法，我能想到的是指数，我们才能做的更好？

How do you partition an array into 2 parts such that the two parts have equal average? Each partition may contain elements that are non-contiguous in the array. The only algorithm I can think of is exponential can we do better?

推荐答案

您可以减少此问题的之子集的问题 - 也是<一个href="http://webcache.googleusercontent.com/search?q=cache%3afYcePS8IwvIJ%3aen.wikipedia.org/wiki/Subset_sum_problem+&cd=1&hl=en&ct=clnk&gl=us">cached这里。这里的想法。

You can reduce this problem to the sum-subset problem - also cached here. Here's the idea.

让 A 是数组。计算 S = A [0] + ... + A [N-1] ，其中 N 的长度 A的。对于 K 从 1 到 N-1 ，让 T_k = S * K / N 。如果 T_k 是一个整数，然后找到 A 的大小 K 的款项 T_k 。如果你能做到这一点，那么你就大功告成了。如果你不能为任何 K 做到这一点，则没有这样的划分存在。

Let A be the array. Compute S = A[0] + ... + A[N-1], where N is the length of A. For k from 1 to N-1, let T_k = S * k / N. If T_k is an integer, then find a subset of A of size k that sums to T_k. If you can do this, then you're done. If you cannot do this for any k, then no such partitioning exists.

下面是这个方法背后的数学。假设有一个分区 A ，使得这两个部位有大小相同的平均说， X X 和是尺寸是是分区，其中 X + Y = N 。然后，你必须有

Here's the math behind this approach. Suppose there is a partitioning of A such that the two parts have the same average, says X of size x and Y of size y are the partitions, where x+y = N. Then you must have

sum(X)/x = sum(Y)/y = (sum(A)-sum(X)) / (N-x)

所以有点代数给出了

so a bit of algebra gives

sum(X) = sum(A) * x / N

由于该数组包含整数，左手侧是整数，所以右侧必须为好。这激发了约束 T_k = S * K / N 必须是整数。剩下的唯一组成部分，是实现 T_k 的尺寸 K 的一个子集的总和。

Since the array contains integers, the left hand side is an integer, so the right hand side must be as well. This motivates the constraint that T_k = S * k / N must be an integer. The only remaining part is to realize T_k as the sum of a subset of size k.

这篇关于你如何分割的阵列分为两部分，使得所述两个部分具有相等的平均？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！