はじめに コード上では変数名としてNDPであったりNextDPと名付けられやすいものです。 正式な名称はよく分かっていないですし、解説されたことがあるのかすら分かっていないテクニックなのですが、どの層でも役に立つもので、使い方やメリットを整理しておこうと思いました。 説明はPythonで行います。ChatGPT-4を使用してC++やRustに置き換えてもらっても動作したので、基本的には別の言語でも使用できるテクニックのはずです。 使い方について まずは基本的なナップサック問題とそのコードを記載します。 実行速度の差をみたいため制約はすこし大きめです。 問題 $N$ 個の品物があります。それぞれ重さが $w_i,ドル 価値が $v_i$ です。 重さの総和が $W$ を超えないように選んだ時の価値の総和の最大値を求めなさい。 制約 1ドル \le N \le 10000$ 1ドル \le W \l