Consider the following problem: Given positive integers $a_1,\ldots,a_n,b_1,\ldots,b_n,A,B$, does there exist a subset $S$ of $\{1,\ldots,n\}$ such that $\sum_{i\in S}a_i\geq A$ and $\sum_{i \in S}b_i\leq B$?

Is this problem NP-hard? I'm thinking there is possibly a reduction from the subset-sum problem, but here there are two lists, and the conditions are inequalities rather than equalities, so I'm not quite sure how to start.

Another remark is that if the condition is just $\sum_{i\in S}a_i\geq A$, then it would be easy because we can check the sum of the whole subset.

  • $\begingroup$ This looks kinda like knapsack. $\endgroup$ – Tom van der Zanden Nov 27 '15 at 8:29

Consider what happens if you set $a_i=b_i$ for all $i$. I expect you should be able to take it from there...


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.