# Finding subset such that one sum is more than target and another sum is less

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.

• This looks kinda like knapsack. Nov 27, 2015 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...