動的計画法によってこの問題を解きます。

高橋君は明日の遠足の準備として、 \(N\) 個のお菓子それぞれについて、\(i = 1, 2, \ldots, N\) の順番で下記の \(3\) つの行動のうちいずれか \(1\) つを行っていくとします。

• \(i\) 番目のお菓子を \(1\) つ目のナップザックに入れる。
• \(i\) 番目のお菓子を \(2\) つ目のナップザックに入れる。
• \(i\) 番目のお菓子を遠足に持っていかないことにする（どちらのナップザックにも入れない）。

遠足の準備の過程で生じる状態であって下記の \(3\) つをすべて満たす状態を状態 \((i, j, k)\) と呼ぶことにします。

• \(1, 2, \ldots, i\) 番目までのお菓子については、すでに上記の \(3\) つの行動のうちいずれかを行なっている。
• \(1\) つ目のナップザックに入っているお菓子の重さの合計は \(j\) である。
• \(2\) つ目のナップザックに入っているお菓子の重さの合計は \(k\) である。

高橋君が遠足の準備を始める前の状態は状態 \((0, 0, 0)\) であり、高橋君がそれぞれのお菓子に対して行動を行うたびに、現在の状態は変化していきます。

動的計画法のDPテーブルとして、\(i = 0,1, \ldots, N\) 、\(j = 0, 1, \ldots, A\) 、\(k = 0, 1, \ldots, B\) に対して、

\(\mathrm{dp}[i][j][k] :=\) （状態 \((i, j, k)\) のときの、「 \(2\) つのナップザックに入っているお菓子の美味しさの合計」としてありうる最大値）

とおきます。ただし、状態 \((i, j, k)\) がそもそも起こり得ない場合は \(\mathrm{dp}[i][j][k] := -\infty\) とします。

このテーブルを埋めることで、本問題の答えが

\[ \max_{\substack{j = 0, 1, \ldots, A \\ k = 0, 1, \ldots, B}} \mathrm{dp}[N][j][k] \]

として得られます。したがって、このDPテーブル \(\mathrm{dp}[\ast][\ast][\ast]\) を埋めることを考えます。

まず、\(\mathrm{dp}[0][\ast][\ast]\) を考えます。 \((0, j, k)\) の形の状態としては、\((0, 0, 0)\) のみが起こり得ます。 そのときにナップザックに入っているお菓子の美味しさの合計は明らかに \(0\) なので、

\[ \mathrm{dp}[0][j][k] = \begin{cases} 0 & (j, k) = (0, 0) のとき\\ -\infty & (j, k) \neq (0, 0) のとき \end{cases} \]

です。 これで、\(\mathrm{dp}[0][*][*]\) が埋まりました。

次に、\(\mathrm{dp}[0][\ast][\ast], \mathrm{dp}[1][\ast][\ast], \ldots, \mathrm{dp}[i-1][\ast][\ast]\) までは埋まっているときに、\(\mathrm{dp}[i][\ast][\ast]\) を埋めることを考えます。 現在の状態を状態 \((i, j, k)\) とし、\(i\) 番目のお菓子に対して \(3\) つの行動のうちのどれを行ったかによって場合分けします。

• \(i\) 番目のお菓子を \(1\) つ目のナップザックに入れたのであれば、入れる前の状態は状態 \((i-1, j-w_i, k)\) であったことになります。また、入れたことによって、\(2\) つのナップザック内のお菓子の美味しさの合計は \(v_i\) だけ増えています。

• \(i\) 番目のお菓子を \(2\) つ目のナップザックに入れたのであれば、入れる前の状態は状態 \((i-1, j, k-w_i)\) であったことになります。また、入れたことによって、\(2\) つのナップザック内のお菓子の美味しさの合計は \(v_i\) だけ増えています。

• \(i\) 番目のお菓子をどちらのナップザックにも入れなかったのであれば、その前の状態は状態 \((i-1, j, k)\) であったことになります。

上記の \(3\) つの場合を考慮すると、

\[ \mathrm{dp}[i][j][k] = \max \lbrace \mathrm{dp}[i-1][j-w_i][k] + v_i, \mathrm{dp}[i-1][j][k-w_i] + v_i, \mathrm{dp}[i-1][j][k]\rbrace \]

です。 ただし、\(j-w_i < 0\) のときは状態 \((i-1, j-w_i, k)\) は起こり得ないので、\(\mathrm{dp}[i-1][j-w_i][k] := -\infty\) とみなします（ \(k - w_i < 0\) のときも同様に \(\mathrm{dp}[i-1][j][k-w_i] := -\infty\) ）。 上記の式によって、\(j = 0, 1, \ldots, A, k = 0, 1, \ldots, B\) について、\(\mathrm{dp}[i][j][k]\) を求めることができます。

上に述べた方法によって、\(i = 0, 1, 2, \ldots, N\) の順番で \(\mathrm{dp}[i][*][*]\) を埋めていくことで、本問題を \(\mathrm{O}(NAB)\) 時間で解くことができます。