Complexity of a weighted subset selection problem. I'm currently thinking about a problem I'd like to manage in one of my applications.

There is a set of objects $\{A, B, C, D, \ldots\}$. Every object has the same attributes with different values. For example, $A$'s attribute $a_1$ has the value $A(a_1)$, $B$'s attribute $a_1$ has the value $B(a_1)$ and so on.

Now I want to pass a number $x$ which represents the maximum number of objects to selected from the set. For example, $x = 2$ would mean that any combination of at most 2 objects are allowed to be selected from the set.

Given this table of attributes and the number $x$, the algorithm should return at most $x$ objects which, in summation, own the largest attributes. Only the greater one counts.

For example: $A,B,C$ with attributes $a_1,a_2,a_3$ and $x = 2$:

$\begin{array}{|c|c|c|c|}
   &amp; a_1 &amp;  a_2 &amp;  a_3\\\hline
 A &amp;   1 &amp; -100 &amp;   -1\\\hline
 B &amp;  -2 &amp;    2 &amp; -200\\\hline
 C &amp; -20 &amp;  -10 &amp;   10\\\hline
\end{array}$

The algorithm should return $A$ and $B$ since $A(a_1) + A(a_2) + B(a_3)$ serve the maximum when at most 2 objects from the set are allowed to be selected.

If I'd use brute-force, I simply would test all $\binom{n}{x}$ combinations and calculate the overall sum.

Is there a faster way to do this?

Thanks!
I'm going to assume your problem is equivalent to what this computes:

max map SubsetsOfSize(N) \S (sum map attributes \A (max map S \e A[e]))


In other words, find the best set of items such that picking the best available item attribute values gives the largest sum.

Yes, it's NP-Complete. You can encode 3-Sat into it. Each variable becomes a true-row and false-row. Each clause becomes a column with a 1 in the rows corresponding to its satisfying assignments. You prevent true-row and false-rows from being selected simultaneously by adding columns with huge values in those two rows (0 everywhere else) and requiring that exactly half the rows be selected (thus the optimal solution will require each huge value, and picking a true and false will lose a huge value somewhere else). The 3-sat instance being satisfiable is equivalent to being able to select items for a total score of HugeValue*NumVariables + NumClauses.

Example transformation:

(A or B or C) and (not A or B or not C)

   uA uB uC  C1 C2
+A  9  0  0  1  0
-A  9  0  0  0  1
+B  0  9  0  1  1
-B  0  9  0  0  0
+C  0  0  9  1  0
-C  0  0  9  0  1
N = 3