# Knapsack like problem with nonnegative weight constraint [closed]

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?

• – D.W.
May 3, 2022 at 18:13
• I’m voting to close this question because it was cross-posted.
– D.W.
May 3, 2022 at 18:13

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