Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 6 / d / 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 computeAn 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.

The optimum is $F_n(W_1,W_2)$, with time $O(n(W_1+1)(W_2+1))$, conventionally $O(n{W}_1{W}_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.