1 次元配列による計算

命題 6.6（「動的計画法」§6）・ ✓公理まで証明済み

長さ $W+1$ の配列 $\kappa$ を $\kappa[j] = 0$ （ $0 \le j \le W$ ）で初期化し、 $i = 1, 2, \ldots, n$ の順に、各 $i$ について $j$ を $W$ から $w_i$ まで降順に動かして

\kappa[j] \leftarrow \max\bigl\{ \kappa[j],\ v_i + \kappa[j - w_i] \bigr\}

と更新する。このとき、 $i$ 回目のループを終えた時点で、すべての $0 \le j \le W$ について $\kappa[j] = K(i, j)$ が成り立つ。とくに全体を終えると $\kappa[W] = K(n, W)$ である。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 1 件、定義なども含めて 2 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

証明で明示的に参照している定理は、まだありません。