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$
0
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 at 13:55

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.