Two-Bag Knapsack Dynamic Programming Algorithm

Definition

Two-Bag Knapsack Dynamic Programming Algorithm

For the Two-Bag Knapsack decision problem, process indexed items $(w_i,p_i)$ one at a time. Store the greatest profit achievable for each pair of exact bag weights:

$$D_i(a,b)=\max \left\{\sum _{j\in I_1\cup I_2}{p}_j:\begin{array}{l}{I}_1,I_2\subseteq \{1,\dots ,i\},I_1\cap I_2=\varnothing ,\\ {\sum }_{j\in I_1}{w}_j=a,{\sum }_{j\in I_2}{w}_j=b\end{array}\right\}.$$

An unreachable state has value $-\infty$. Each item is skipped, placed in bag 1, or placed in bag 2. Accept precisely when some final state satisfies
$a\le W_1,b\le W_2,D_r(a,b)\ge t.$
This dynamic programme is pseudopolynomial and becomes polynomial when the input integers are encoded in unary, including for signed weights.

State space and recurrence

Bound every reachable weight, not just the final capacities

Define

$$L=\sum _{i=1}^r\min (w_i,0),U=\sum _{i=1}^r\max (w_i,0),R=U-L+1=1+\sum _{i=1}^r|w_i|.$$

Every subset of items has total weight in the integer interval $[L,U]$. Thus each bag needs $R$ possible weight indices. Negative indices can be stored at array offset $a-L$.

With signed weights, an intermediate weight above a capacity may later fall below it. For weights $5,-4$ and capacity $1$, selecting both gives a feasible final weight despite the intermediate weight $5$.

Therefore the signed-weight algorithm applies the capacity bounds only when examining the final layer. It does not discard intermediate states merely for exceeding $W_1$ or $W_2$.

Keep the best profit for each exact weight pair

Initialise $D_0(0,0)=0$ and every other state to $-\infty$. For $1\le i\le r$,

$$D_i(a,b)=\max \{\begin{array}{ll}{D}_{i-1}(a,b)& \text{skip item }i,\\ D_{i-1}(a-w_i,b)+p_i& \text{put item }i\text{ in bag 1},\\ D_{i-1}(a,b-w_i)+p_i& \text{put item }i\text{ in bag 2}.\end{array}$$

A lookup outside $[L,U{]}^2$ returns $-\infty$, and $-\infty +p_i=-\infty$. Each transition reads the previous layer, so even zero-weight items cannot be reused.

Two partial assignments with the same exact weights leave identical choices for the remaining items. Keeping only the greater profit cannot destroy a solution: every continuation adds the same weights and profit to either assignment.

Pseudocode

L = sum(min(w[i], 0) for i = 1,...,r)
U = sum(max(w[i], 0) for i = 1,...,r)
previous[a,b] = -infinity for all a,b in [L,U]
previous[0,0] = 0
 
for i = 1,...,r:
    current[a,b] = -infinity for all a,b in [L,U]
    for a,b in [L,U]:
        current[a,b] = max(
            previous[a,b],
            lookup(previous, a-w[i], b) + p[i],
            lookup(previous, a, b-w[i]) + p[i]
        )
    previous = current
 
return any(previous[a,b] >= t
           for a,b in [L,U] with a <= W1 and b <= W2)

Here lookup returns $-\infty$ outside the table. The two arrays are separate layers; after swapping them, the next output layer is reinitialised.

Correctness

The table has the stated meaning at every layer

Base layer

With no items, the only assignment has weights $(0,0)$ and profit $0$. Every other exact weight pair is unreachable, matching $D_0$.

Exhaust all assignments by the last item's destination

Assume layer $i-1$ is correct. Every assignment of the first $i$ items places item $i$ in exactly one of the three destinations. Removing it produces the predecessor weights in the corresponding recurrence term. Its profit is the predecessor profit plus $p_i$ if selected, or unchanged if skipped. Hence no assignment beats the maximum in the recurrence.

Conversely, each finite recurrence term is attained by a predecessor assignment, extended by the indicated destination. Thus the maximum is attainable. This proves the invariant for layer $i$.

Apply the final constraints

Every complete assignment appears in layer $r$ at its exact weight pair, and every finite entry represents such an assignment. Testing the two weight bounds and profit threshold therefore accepts exactly the yes-instances.

Running time and encoding

There are $(r+1)R^2$ states and at most three candidates per state. The algorithm uses $O((r+1)R^2)$ arithmetic operations and $O(R^2)$ stored profit values with rolling layers.

Let $P={\sum }_i|p_i|$. Every finite table value has magnitude at most $P$, so arithmetic takes polynomial time in the bit length of $P$. The operation bound is not a claim that arbitrary-size integer arithmetic costs one bit operation.

For unary input length $N$,

$$\underset{\text{items}}{\underbrace{r}}=O(N),\underset{\text{weight range}}{\underbrace{R=1+\sum _i|w_i|}}=O(N),P=O(N).$$

Consequently there are $O(N^3)$ arithmetic operations on $O(\log (N+1))$-bit profits, giving polynomial bit complexity. Under binary encoding, $R$ may be exponential in $N$; the same algorithm is only pseudopolynomial.

Nonnegative-weight restriction

If all weights and capacities are nonnegative, an over-capacity state can never become feasible later. Restrict the two axes to $0\le a\le W_1$ and $0\le b\le W_2$. The same recurrence then uses

$O((r+1)(W_1+1)(W_2+1))$

arithmetic operations. The additions of $1$ account for zero weights and zero capacities. Negative profits do not invalidate either recurrence; skipping and taking maxima handle them directly.