Two-Bag Knapsack Decision Problem

Definition

Two-Bag Knapsack Decision Problem

Instance: Indexed items $(w_i,p_i)\in {\mathbb{Z}}^2$ for $1\le i\le r$, two weight bounds $W_1,W_2\in \mathbb{Z}$, and a profit threshold $t\in \mathbb{Z}$. Integers are encoded in binary unless specified otherwise.

Question: Are there disjoint index sets $I_1,I_2\subseteq \{1,\dots ,r\}$ such that

$$\sum _{i\in I_1}{w}_i\le W_1,\sum _{i\in I_2}{w}_i\le W_2,\sum _{i\in I_1\cup I_2}{p}_i\ge t?$$

Each item is placed in the first bag, placed in the second bag, or skipped. Equal pairs at distinct indices are distinct items. This signed-integer formulation allows negative weights and profits; the usual nonnegative-weight restriction additionally requires $w_i,W_1,W_2\ge 0$.