# For efficient algorithm on “minimization” knapsack problem

Suppose there are two arrays of positive numbers, $a[\cdot]$ and $b[\cdot]$, and value $B>0$. How to pick a set of indexes $I$, so that

$\sum_{i\in{I}}{b[i]}\geq{B}$

To minimize $\sum_{i\in{I}}{a[i]}$

I know this problem sounds like knapsack problem, but the objective is really to minimise, not maximise. Does this make a difference if I want to seek a polynomial-time, approximate algorithm?

There's a simple reduction from knapsack. Binary search for the solution to your knapsack instance, then solve the "dual knapsack" with that value as your covering constraint $B$. Compare the value given by the "dual knapsack" against your knapsack packing constraint, which gives you the direction to continue the binary search.