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!!
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityGiven 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!!
This is at least as hard as the Subset Sum problem, hence, yes it is NP-hard.