Given a set of real numbers, choose a subset to maximize the average subject to the average not exceeding a given threshold. Is it NP hard?
I think so, but I cannot come out with a proof. Thanks a lot!!
Add a comment
|
$\begingroup$
$\endgroup$
3
This is at least as hard as the Subset Sum problem, hence, yes it is NP-hard.
answered Jul 18 '18 at 22:47
-
$\begingroup$ Any suggestions for a rigorous proof? Thanks much! $\endgroup$ – Tomlin Jul 19 '18 at 1:12
-
$\begingroup$ Hint: for nonempty $S$, $\textrm{average}(S) \leq 0 \leftrightarrow \textrm{sum}(S)\leq 0$. $\endgroup$ – Yonatan N Jul 19 '18 at 4:40
-
$\begingroup$ Can you give more hint please? I do not know how to handle the cardinality $|S|$. $\endgroup$ – Tomlin Jul 20 '18 at 6:02
