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?



Knapsack like problem with nonnegative weight constraint
Assuming $x\_i$ is binary, perform a change of variables $\bar{x}\_i:=1-x\_i$ where $w\_i>0$:
\begin{align}
\sum\_i w\_i x\_i 
&= \sum\_{i:w\_i>0} w\_i x\_i + \sum\_{i:w\_i<0} w\_i x\_i \\
&= \sum\_{i:w\_i>0} w\_i(1-\bar{x}\_i) + \sum\_{i:w\_i<0} w\_i x\_i \\
&= \sum\_{i:w\_i>0} w\_i + \sum\_{i:w\_i>0} (-w\_i)\bar{x}\_i + \sum\_{i:w\_i<0} w\_i x\_i
\end{align}
So $\sum\_i w\_i x\_i \ge 0$ is equivalent to
$$\sum\_{i:w\_i>0} w\_i\bar{x}\_i + \sum\_{i:w\_i<0} (-w\_i) x\_i \le \sum\_{i:w\_i>0} w\_i$$


