What is the name of the algorithm that “inverts” the knapsack problem?

I know of the knapsack problem. I want to find an algorithm that "inverts" the knapsack problem. My problem is as follows:

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is greater than or equal to a given limit and the total value is as small as possible.

$$\min \sum _{i=1}^{n}v_{i}x_{i}$$ subject to

$$\sum _{i=1}^{n}w_{i}x_{i}\geq W$$

Is it still NP-hard problem?

• Note that this is simply the dual version of the knapsack problem. It is weakly NP-hard and can be solved with dynamic programming. – Kuifje Sep 6 '16 at 14:52

I think the answer is yes, if the # of each item is bounded. Suppose you have two bags, namely, $B_1$ and $B_2$ and you want to distribute the items into these two bags. You want to determine the # of each item to include in $B_1$ such that $$\sum_{i=1}^n v_ix_i$$ is minimized and at the same time, $$\sum_{i=1}^n w_ix_i \geq W$$ This is equivalent to determining the # of each item to include in $B_2$ such that $$\sum_{i=1}^n v_ix_i$$ is maximized and at the same time, $$\sum_{i=1}^n w_ix_i \leq W'$$ where $W' = \text{total weights of the items } - W$.
• @user3051460 If I understand correctly, what you have computed are items that should be put in $B_2$. If you remove these items, the remaining items are what you want. – PSPACEhard Sep 5 '16 at 14:27
• @user3051460 $>W$ is equivalent to $\geq W + 1$ if weights are integers. – PSPACEhard Sep 5 '16 at 14:43
• @user3051460 I think it is possible to choose $[2, 5]$ instead, but this is not about the problem itself but about how you implement the algorithm, e.g., how you implement the dynamic programming. – PSPACEhard Sep 5 '16 at 14:59