スポンサーリンク

再帰を使った場合

参考:[c言語]フィボナッチ数列を動的計画法でコーディング

容量Wmaxのナップザックに、N個の品物を入れる。
品物iの重さがw[i] 価値がv[i]であるときに、容量Wmaxを超えない、
かつ、価値が最大となるように品物を選択してナップザックに詰める。
その時の価値を求めます。

まずは、再帰を使った全探索の方法です。

下記がサンプルコードになります。

ポイントは下記の部分ですね。

下記が実行結果になります。

スポンサーリンク

動的計画法のメモ化再帰を使った場合

次は、メモ化再帰の方法です。

ポイントは下記の一度計算していたら、計算はスキップしてメモデータの値を返す箇所です。

計算していなければ、計算してメモデータに結果を格納します。

下記が実行結果になります。

動的計画法で漸化式を使った場合

最後に漸化式を使った場合です。

ポイントはほぼコード全てになりますが下記ですね。

下記が実行結果になります。

スポンサーリンク