我最近遇到了以下问题，但到目前为止还不知道如何解决。
让S = {1 v <子>,v <子> 2子> 3 ,…， vn}是定义在∈6上的n个数组的集合。也就是说，每个数组有6个条目。
对于给定的数组集合，设维度的平均值为该集合中所有元素对应维度的坐标之间的平均值。
同样，让我们定义数组集合的某个属性 p 作为集合的所有均值(总共有6个均值，每个维度一个)中的最小值。例如，如果某集合的维数为{10,4,1,5,6,3}，则P为1。
现在到问题的定义:返回S的所有子集S'中的最大基数，使得 p (S')≥T， T为已知的阈值，如果这样的子集不存在，则返回0。另外，输出任意最大值S'(使得P(S')≥T)。
summary:输入:集合S和阈值t。输出:某个子集S' (|S'|显然是直接的)。
我开始试图想出一个贪婪的解决方案，但没有成功。然后，我转向动态规划方法，但无法建立解决问题的递归。我可以进一步阐述一下我对解决方案的想法，但考虑到我已经取得的进展(或没有取得的进展)，我认为它们不会有多大用处。
任何帮助都将非常感激!
通过递归的暴力破解计算将具有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，但为了清晰起见，我在这里包含了它