algorithm - 均值大于阈值的数组的最大子集

Question

我最近遇到了以下问题，到目前为止还不知道如何解决它。

Let S = {v₁, v₂, v₃, ..., v_n} be a set of n arrays defined on the ℝ⁶. That is, each array has 6 entries.

For a given set of arrays, let the mean of a dimension be the average between the coordinates corresponding to that dimension for all elements in the set.

Also, let us define a certain property P of a set of arrays as the lowest value amongst all means of a set (there is a total of 6 means, one for each dimension). For instance, if a certain set has {10, 4, 1, 5, 6, 3} as means for its dimensions, then P for this set is 1.

Now to the definition of the problem: Return the maximum cardinality amongst all the subsets S' of S such that P(S') ≥ T, T a known threshold value, or 0 if such subset does not exist. Additionally, output any maximal S' (such that P(S') ≥ T).

Summarising: Inputs: the set S and the threshold value T. Output: A certain subset S' (|S'| is evidently immediate).

我首先开始尝试提出一个贪婪的解决方案，但没有成功。然后，我转向动态编程方法，但无法建立解决问题的递归。我可以进一步扩展我对解决方案的想法，但我认为它们不会有多大用处，因为我已经取得了多大进展(或没有取得进展)。

如有任何帮助，我们将不胜感激!

Answer 1

通过递归进行暴力评估的时间复杂度为 O(2^n)，因为每个数组都可以存在于子集中，也可以不存在。

解决此问题的一种(仍然低效但稍微好一些)方法是借助整数线性规划。

Define Xi = { 1 if array Vi is present in the maximal subset, 0 otherwise }
Hence Cardinality k = summation(Xi) {i = 1 to n }

此外，由于所有维度的平均值 >= T，这意味着:

d11X1 + d12X2 + ... + d1nXn >= T*k
d21X1 + d22X2 + ... + d2nXn >= T*k
d31X1 + d32X2 + ... + d3nXn >= T*k
d41X1 + d42X2 + ... + d4nXn >= T*k
d51X1 + d52X2 + ... + d5nXn >= T*k
d61X1 + d62X2 + ... + d6nXn >= T*k

Objective function: Maximize( k )

实际上，您应该通过基数方程消去 k，但为了清楚起见，我将其包含在此处。