No Caffeine, No Life

プログラミング(主にPython)

AOJ DPL_1_B:ナップザック問題 動的計画法

問題:

ナップザック問題 | 動的計画法 | Aizu Online Judge

解説:

  • {\displaystyle dp[ i ] [ j ] }{\displaystyle i }種類の品物を用いて大きさ{\displaystyle j }のナップザックに入れる場合の価値の最大値
  • {\displaystyle items [ i ] }:品物の価値{\displaystyle v }と重さ{\displaystyle w }のリスト

と置いたとき、{\displaystyle dp[ i ] [ j ] }は、

  • {\displaystyle dp[ i-1 ] [ j ] }
  • {\displaystyle dp[ i-1 ] [ j - 品物iの重さ ] + 品物iの価値 }
  • の、最大値で決まる。

解答例: