4
$\begingroup$

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?

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

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$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user3051460 Sep 5 '16 at 14:22
  • $\begingroup$ @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. $\endgroup$ – PSPACEhard Sep 5 '16 at 14:27
  • $\begingroup$ Thanks. It means weights=[3,5]. Is it right? $\endgroup$ – user3051460 Sep 5 '16 at 14:28
  • 1
    $\begingroup$ @user3051460 $>W$ is equivalent to $\geq W + 1$ if weights are integers. $\endgroup$ – PSPACEhard Sep 5 '16 at 14:43
  • 1
    $\begingroup$ @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. $\endgroup$ – PSPACEhard Sep 5 '16 at 14:59

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.