1
$\begingroup$

I am dealing with a knapsack-like problem with one difference from the conventional problem: the “weights” can be positive or negative and the constraint is $\sum w_i x_i \ge 0$ instead of $\sum w_i x_i \le W$. The "values" can also be positive or negative.

Can this be transformed to a knapsack problem or is it some other type of combinatorial optimization problem?

$\endgroup$
2

1 Answer 1

1
$\begingroup$

If the values $v_i$ of the items are non-negative you can simply "buy" all items with positive weights. Let $S = \{i \mid w_i \le 0\}$, $W = \sum_{i \not\in S} w_i$ and $V = \sum_{i \not\in S} v_i$. Your problem then becomes a standard Knapsack problem:

$$ \max \sum_{i \in S} y_i v_i \quad \mbox{s.t.}\\ \sum_{i \in S} -w_i y_i \le W, \\ y_i \in \{0,1\} \quad \forall i \in S. $$

Once a solution for the new problem is found, a solution for the original problem can be recovered by setting: $$ x_i = \begin{cases} y_i & i \in S \\ 1 & i \not\in S \end{cases} $$

The value of the new solution will be $\sum_i x_i v_i = V + \sum_{i \in S} y_i v_i$.

$\endgroup$
1
  • $\begingroup$ Thanks both, for the nice solution! I guess with the nonnegative constraint you meant the other way around -- buy all items with positive weights and then choose negative-weight items using knapsack solution? Then it will go through. Sorry I forgot to mention that the values can also be negative, so that potentially positive-weight items with negative value can be used to provide "space" for negative-weight items with (more) positive value? $\endgroup$
    – Jeffrey
    Oct 3, 2021 at 13:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.