\(i\) 番目の数値まで処理したときに計算結果を \(j\) にできるかどうかを \(B(i, j)\) とする. このとき,

\[\begin{align} B(i, j) & \rightarrow B(i-1, j-Wi) \\ B(i, j) & \rightarrow B(i-1, j/Wi) \end{align}\]

を使って DP で更新していく.

更新が終わったら, \(B(1, W_1)\) から始めて, \(B(i+1, j+W_i)\) か \(B(i+1, j \cdot W_i)\) のうち \(\mathrm{true}\) になっている方 (どちらも辿れる場合は + を優先する) を辿っていって \(B(N, Total)\) に辿り着くルートを構築する.