No Caffeine, No Life

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

AOJ DPL_1_C:ナップザック問題 (同じ種類の品物はいくつでも選ぶことができる場合) 動的計画法

問題:

Knapsack Problem | 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の価値 }
  • {\displaystyle dp[ i ] [ j - 品物iの重さ ] + 品物iの価値 }
  • の、最大値で決まる。(この3点目が、重複を許して選ぶことに相当)

解答例: