エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
知名度がいまいち分かってないNextDPというテクニックについて - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
知名度がいまいち分かってないNextDPというテクニックについて - Qiita
はじめに コード上では変数名としてNDPであったりNextDPと名付けられやすいものです。 正式な名称はよく... はじめに コード上では変数名としてNDPであったりNextDPと名付けられやすいものです。 正式な名称はよく分かっていないですし、解説されたことがあるのかすら分かっていないテクニックなのですが、どの層でも役に立つもので、使い方やメリットを整理しておこうと思いました。 説明はPythonで行います。ChatGPT-4を使用してC++やRustに置き換えてもらっても動作したので、基本的には別の言語でも使用できるテクニックのはずです。 使い方について まずは基本的なナップサック問題とそのコードを記載します。 実行速度の差をみたいため制約はすこし大きめです。 問題 $N$ 個の品物があります。それぞれ重さが $w_i$, 価値が $v_i$ です。 重さの総和が $W$ を超えないように選んだ時の価値の総和の最大値を求めなさい。 制約 $1 \le N \le 10000$ $1 \le W \l