In depth-first search, mark every vertex white initially. At a white start vertex $u$, increment a global clock, record $d[u]$ and color it gray. Scan its outgoing adjacency list; recursively visit each still-white neighbor, recording the discovery edge. After all neighbors have been processed, color $u$ black, increment the clock and record $f[u]$. Start again from every remaining white vertex to obtain a forest. Each vertex is discovered once and each edge scanned once, so the time is $O(|V|+|E|)$ with adjacency lists.

The DFS parenthesis property says that for distinct vertices $u,v$, their intervals $[d[u],f[u]]$ and $[d[v],f[v]]$ are disjoint or one lies strictly inside the other. Moreover $v$ is a proper descendant in a rooted tree of $u$ exactly when $d[u]<d[v]<f[v]<f[u]$. A recursive call finishes before its caller returns, while completed calls from separate branches have disjoint intervals; these two possibilities prove the property.

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.

For the unbounded knapsack problem, let $F(c)$ be the greatest total value obtainable with weight at most capacity $c$. Assume positive integer item weights and nonnegative integer capacity $W$. Set $F(0)=0$, and fill increasing capacities usingThe zero alternative permits unused capacity. If a nonempty optimum includes item $i$, removing one copy leaves a feasible smaller-capacity instance; its remaining value cannot exceed $F(c-w_i)$. Conversely every candidate in the displayed maximum is feasible, proving equality. The smaller-capacity state allows the same type again, implementing repetition.

The answer is $F(W)$, computed in $O(nW)$ time and $O(W)$ space. Record an attaining item at each state to reconstruct the multiset. This is pseudopolynomial time, because $W$ is a number whose binary representation may have only $O(\log W)$ bits. A positive-value zero-weight type would make the optimum unbounded and must be excluded or detected separately.