漸化式を立てる練習（１）

• 合計金額 n=5
• コイン{ 1, 2, 3 } を使って支払うと考える

• 記号の意味
  • v:コインの価値
  • 表の横軸はコインの枚数制限(j)
  • 表の縦軸はコインを見に行くインデックス(i)
  • 表の二次元配列は C[N+1][W+1] ← C[コインの数+1][枚数制限+1]

• 漸化式
  • dp[i+1][j] = \begin{eqnarray} \left\{ \begin{array}{l} 1 (i = 1) \\ dp[i][j] + dp[i+1][j - v[i+1]] \end{array} \right. \end{eqnarray}

• カードの合計枚数 N=4, 求める平均値 A=8
• カード{ 7, 9, 8, 9 } を使うと考える

• 記号の意味
  • v:カードの数値
  • 表の横軸はカードの合計の平均値(j)
  • 表の縦軸はカードを見に行くインデックス(i)
  • 表の二次元配列は C[N+1][A+1] ← C[カードの数+1][求める平均値+1]
  • C[][]の中身は平均をAにする場合の数

• 漸化式
  • dp[i+1][j] = \begin{eqnarray} \left\{ \begin{array}{l} 1 (i = 1) \\ dp[i][j] + dp[i+1][j - v[i+1]] \end{array} \right. \end{eqnarray}

参考：4.5 0/1 Knapsack - Two Methods - Dynamic Programming

• 記号の意味
  • v:価値, w:重さ
  • 表の横軸はナップサックの容量制限(j)
  • 表の縦軸は品物を見に行くインデックス(i)
  • 表の二次元配列は C[N+1][W+1] ← C[品物の数+1][容量+1]

• 漸化式
  • dp[i+1][j] = \begin{eqnarray} \left\{ \begin{array}{l} dp[i][j] (j < w[i]) \\ max(dp[i][j], dp[i][j-w[i]]+v[i]) \end{array} \right. \end{eqnarray}

• 漸化式の２行目の意味がいつもわからなくなる
  • 01ナップサックは要は全探索なので、各セルでの操作は取る/取らないを表す
  • dp[i][j]は取らない, dp[i][j-w[i]]+v[i] は取る場合を表すと考える

• ここから 緑コーダーが頑張ってDPを使ったナップサック問題に挑戦してみた

[品名], [カロリー], [値段], [塩分]
やわらかチキンのサラダ,134,299,1.2
半熟卵とポークのサラダ,433,599,2.3
ほうれん草のソテー,80,189,1.0
フレッシュチーズとトマトのサラダ,169,299,1.1
プロシュート(パルマ産熟成生ハム),225,399,2.7
辛味チキン,333,299,2.3
チョリソー(辛味ソーセージ),380,399,2.5
マルゲリータピザ,568,399,2.5
パンチェッタのピザ,646,399,2.4
アラビアータ,591,399,3.7
ミートソースボロニア風,538,399,3.6
ミラノ風ドリア,519,299,2.7
半熟卵のミラノ風ドリア,609,368,2.9
柔らかチキンのチーズ焼き,549,499,2.0
ミルクジェラート,100,199,0.1
イタリアンプリン,216,249,0.1

• 漸化式
  • dp[i+1][j] = \begin{eqnarray} \left\{ \begin{array}{l} dp[i][j] (j < m[i]) \\ max(dp[i][j], dp[i][j-m[i]]+c[i]) \end{array} \right. \end{eqnarray}

• M=60, N=3 とする
• 1 ≦ M ≦ 200000 なので横軸は20万に設定しとけばいいのかな AtCoderならそこまで要求されるが、paizaは優しい
• 最小化をするので初期化はINFを使う
• 表の二次元配列は C[N+1][M+1] ← C[会社の数+1][M+1]

• 初期

• 遷移

• 漸化式
  • dp[i+1][j] = \begin{eqnarray} \left\{ \begin{array}{l} min(dp[i][j], Ri ) ( Qi >= j ) \\ min(dp[i][j], dp[i][j-Qi] + Ri) \end{array} \right. \end{eqnarray}

• 式の意味
  • Qi >= jのとき: min(dp[i][j], Ri )
  • Qi < jのとき: min(dp[i][j], dp[i][j-Qi] + Ri )

• 無事正解できた
  • POH! Lite soregashi_boxさんの採点結果

# coding: utf-8
lines = <<'EOS'
250
5
35 3640
33 2706
98 9810
57 5472
95 7790
EOS

# lines = $stdin.read
array = lines.split("\n")
M = array[0].to_i
N = array[1].to_i

INF = Float::INFINITY
MAX_M = M

Item = Struct.new(:q, :r)

items = [Item.new(0,0)]
array[2..array.length].each do |s|
  item = Item.new
  item.q, item.r = s.split(" ").map(&:to_i)
  items << item
end

# 二次元dp
dp = Array.new(N+1).map{Array.new(MAX_M+1, INF)}
for i in 1...N+1
  for j in 1...M+1
    if items[i].q >= j
      dp[i][j] = [dp[i-1][j], items[i].r].min
    else
      dp[i][j] = [dp[i-1][j], dp[i-1][j-items[i].q] + items[i].r].min
    end
  end
end

ans = INF
dp.each do |line|
  ans = [line[M], ans].min
end

puts ans