<p>This is at least as hard as the Subset Sum problem, hence, yes it is NP-hard.</p>

CC BY-SA 4.0
2018-07-19T01:12:15.827Z
Any suggestions for a rigorous proof? Thanks much!
Tomlin
CC BY-SA 4.0
2018-07-19T04:40:57.163Z
Hint: for nonempty $S$, $\textrm{average}(S) \leq 0 \leftrightarrow \textrm{sum}(S)\leq 0$.
Yonatan N
CC BY-SA 4.0
2018-07-20T06:02:09.040Z
Can you give more hint please? I do not know how to handle the cardinality $|S|$.
Tomlin
CC BY-SA 4.0
2018-07-18T22:47:59.003Z
2018-07-18T22:47:59.003Z
Konstantinos Koiliaris
<p>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? </p>

<p>I think so, but I cannot come out with a proof. Thanks a lot!!</p>

<np-hardness>
Is choosing a subset to maximize the average its members, an NP hard problem?
Tomlin
# Is choosing a subset to maximize the average its members, an NP hard problem?

(Asked by: username_0 on 2018-07-18)

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!!

**Tags:** np-hardness

---

## 1 answers

### Answer by username_1 on 2018-07-18. Score: 2

This is at least as hard as the Subset Sum problem, hence, yes it is NP-hard.

> **Comments:**
> **username_0**: Any suggestions for a rigorous proof? Thanks much!  
> **username_2**: Hint: for nonempty $S$, $\textrm{average}(S) \leq 0 \leftrightarrow \textrm{sum}(S)\leq 0$.  
> **username_0**: Can you give more hint please? I do not know how to handle the cardinality $|S|$.  

---

