= Solution
Each physical item may enter neither knapsack or exactly one of them. Let $F_i(a,b)$ be the largest combined value using the first $i$ items with remaining capacity limits $a,b$. Initialize $F_0(a,b)=0$ and compute
$$
F_i(a,b)=\max\begin{cases}
F_{i-1}(a,b),\\
v_i+F_{i-1}(a-w_i,b)&\text{if }w_i\leq a,\\
v_i+F_{i-1}(a,b-w_i)&\text{if }w_i\leq b.
\end{cases}
$$
An infeasible alternative is omitted. The three alternatives classify the placement of item $i$ exhaustively. Every reference uses row $i-1$, ensuring that no item is placed in both knapsacks. Removing item $i$ from an optimum and applying <optimal substructure> proves the <recurrence relation>.
\b[The optimum is $F_n(W_1,W_2)$], with time $O(n(W_1+1)(W_2+1))$, conventionally $O(nW_1W_2)$ for positive capacities. Two successive layers require $O((W_1+1)(W_2+1))$ space; keep predecessor decisions or recompute them if the actual allocations are wanted. The stipulated uniqueness of values and weights is unnecessary for correctness. The capacity-indexed algorithm is <pseudopolynomial>.
Back to article page
