4
$\begingroup$

The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$:

$ max \displaystyle\sum_{i} x_i, x_i \in \{0,1\} $

subject to

$ \displaystyle\sum_{i} w_ix_i \leq W $

for a maximum weight $W$.

Recall that the weights in this version can be negative: we will simply select all items with zero or negative value and then solve for the remaining items with positive weight[1]

Now suppose we also want to limit the maximum weight on the negative side:

$ |\displaystyle\sum_{i} w_ix_i| \leq W $

We can quickly see that this problem is still hard when we set $W=0$ as this would answer subset-sum.

What is the name of the problem where we have constraints on the absolute weight? As I encounter instances of this problem often I would like to read up on it and possible heuristics. I suspect that it would have long been listed as a variant of subset-sum or knapsack but I fail to find this exact problem.


[1].

$ \displaystyle\sum_{i} \{ w_ix_i | w_i \in w^+ \} \leq W - \displaystyle\sum_{i} \{ w_i | w_i \in w^- \} $

$\endgroup$
  • $\begingroup$ Maybe I'm missing something, but the constraint for the absolute values of the weights is exactly the same problem as the "normal" constraint in the case that all weights are non-negative. $\endgroup$ – gnasher729 Oct 15 '16 at 16:02
  • 1
    $\begingroup$ The problem that you call "the classical 0, 1 knapsack problem with unit values" can be solved optimally in $O(n\log n)$ time by greedily grabbing items in order of increasing weight (this also does the right thing when the weights can be negative). $\endgroup$ – j_random_hacker Oct 24 '16 at 11:25
  • $\begingroup$ As someone already mentioned, your classical problem is polynomial. Items must have different values in the classical Knapsack. $\endgroup$ – Parham Oct 25 '16 at 11:05
  • $\begingroup$ When $W=0$, this is related to the Partition problem. You might like to look up heuristics and approximation algorithms for that problem and see if they can be applied to your problem. $\endgroup$ – D.W. Apr 22 '17 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.