Background
In the classic formulation of the knapsack problem with both weight and volume constraints, we are given a collection of $n$ items where item $i$ has weight $w_i\in\mathbb{N}$, volume $u_i\in \mathbb{N}$, and value $v_i\in\mathbb{N}$. We aim to fill a bag with weight capacity $W$ and volume capacity $U$ such that we maximize the total value of the items in the bag.
Let $x_i\in\{0, 1\}$ be a binary indicator of selecting item $i$ (putting it in the bag), then the problem is given as,
$$ \max_{\mathbf{x}\in \{0, 1\}^n} \sum_{i=1}^n v_i x_i \qquad \text{s.t }\sum_{i=1}^n w_i x_i \leq C \quad \text{ and } \quad \sum_{i=1}^nu_i x_i \leq U$$
This is known to be solvable via dynamic programing in time $O(n W U)$.
Now consider a modified version of knapsack in which weights and values can be negative, i.e. $w_i, v_i\in \mathbb{Z}$, but volume is still positive, i.e. $u_i\in \mathbb{N}$. Moreover, instead of the weight constraint being given as an bound on total weight it is given as a bound on the absolute value of total weight. Then the goal is to solve, $$ \max_{\mathbf{x}\in \{0, 1\}^n} \sum_{i=1}^n v_i x_i \qquad \text{s.t }\bigg|\sum_{i=1}^n w_i x_i \bigg|\leq C \qquad \text{ and } \qquad \sum_{i=1}^n u_ix_i\leq U $$
Questions
1.) Is this version of knapsack well studied?
2.) Does this version of knapsack emit a dynamic programing solution, and if so what is the complexity?
Thoughts so Far
Ignoring the volume constraint and absolute value constraint, when weights and values can be positive or negative the problem can be solved with a similar approach to that of the classic formulation. If any item $i$ has $v_i \geq 0$ and $w_i \leq 0$, always place $i$ in the knapsack. Let $U = \{i : v_i \geq 0 \text{ and } w_i \leq 0\}$ and define a new capacity be $C' = C + \sum_{i\in U} w_i$. Items with $v_i \leq 0$ and $w_i \geq 0$ will never be included in the knapsack so we may disregard these items. For any item $i$ with $v_i \leq 0 $ and $w_i\leq 0$, we can create an alternate item $i'$ where $v_{i'} = -v_i$ and $w_{i'} = w_i$. The alternate item $i'$ represents the effect of not including $i$ in our solution. Let $S_1 = \{i: v_i \geq 0 \text{ and } w_i \geq 0\}$ and $S_2 = \{j': v_j \leq 0 \text{ and } w_j \leq 0\} $.
Then by using capacity $C'$ and items $S_1\cup S_2$ we recover a classic knapsack problem since all weights and values are nonnegative.
However, this no longer works when adding the absolute value constraint since we may want to include items with negative value and positive weight, and may want to not include items with positive value and negative weight, i.e. the decision on items of the form $v\leq 0$ and $w\geq 0$ or $v\geq 0$ and $w\leq 0$ is no longer straightforward.
Moreover, in the classic dynamic programing approach, once the capacity constraint is violated, we need not continue searching since the capacity constraint cannot be fixed. However in the modified version, since we cannot remove negative weights (in the manner previously mentioned) it may be the case that the capacity constraint can be resatisfied through searching.
My instinct in this case is to try some type of item pairing, in which we match items with negative and positive weight, in essence "paying" for items with other items. This stems from the notion that we would only ever want to take an item negative value if it somehow allowed us to take an item (or items) with greater value. If some item has large weight and large value, then we may be able to take this item, and "pay" for it by adding smaller items with negative weight, so long as their cumulative value does not negate the value of the large item. But this is proving hard to operationalize.
Moreover, when adding back in the volume constraint, things become more complicated.
Any help would be greatly apricated!
