# 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$.
• I tested it but it looks wrong. First, I download a MATLAB code which in kr.mathworks.com/matlabcentral/fileexchange/22783-0-1-knapsack/…. then I apply the code with weights = [1, 2, 3, 1, 5]; values = [1, 1, 1, 1, 1]; total_weight=sum(weights); W=8; W_prime=total_weight-W [best amount] = knapsack(weights, values, W_prime) . It does not show what I expected. For example, amounts return the options w={1 2 1} does not true – user3051460 Sep 5 '16 at 14:22
• @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
• Thanks. It means weights=[3,5]. Is it right? – user3051460 Sep 5 '16 at 14:28
• @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