動的計画法 - ナップサック問題

[アルゴリズム,DP]

動的計画法 - ナップサック問題

これを先に考えるより、動的計画法 - コイン問題の練習問題を解いておいたほうが良いかもしれない。

備考

• ナップサック問題は、数学の分野でいうと 整数計画問題 の一種であるようだ
• 整数計画問題からは, 巡回セールスマン問題や最大クリーク問題などが競プロの問題として出題されるのを見たことがある

  問題設定

理解のために

• Wikipedia - ナップサック問題
  • 「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」
  • 競技プログラミングの世界ではたぶん常識問題で、応用情報技術者試験でも最近出てた

…

• 動的計画法（ナップサック問題） から、動的計画法によるメモ化を学びましょう。
• 蟻本にはより詳細なナップサック問題の解説が載っているので、それを読むことがおすすめ。

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

指針

• 問題を解いていく手段はいくつかある
  • 深さ優先探索による総当たり
  • メモ化再帰による実装
  • 漸化式を用いた実装

→　現実的には、メモ化再帰・漸化式を使いこなしていくことが必要

  ナップサック問題のパターン

• AOJ - Combinatorial - 0-1 Knapsack Problem - 解説

01ナップサック問題

問題

重さと価値がそれぞれ Wi, Vi であるようなN個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。

方針

(1) 品物の価値と重さを記録する配列 (2) i番目までの品物を考慮して大きさwのナップサックに入れる場合の価値の合計の最大値をC[i][w]とする２次元配列を準備する

実際に解いてみる

items[N+1] 品物の価値と重さを記録 / C[N+1][W+1] i番目までの品物を考慮して大きさwのナップサックに入れる場合の価値の合計の最大値

(手順0) items[N+1] として、品物の価値と重さを保存しておく

(手順1) 以下の場合は２次元配列の価値が0になるので、0埋めしておく

• ナップサックの大きさw=0のとき
• 品物の数iが0個の場合

• 二次元配列は C[N+1][W+1] ← C[品物の数+1][容量+1]
• 縦軸は品物の個数、横軸は容量

(手順2) 品物1までを見ていく

• ナップサックの大きさが1のときは品物を入れられないので C[1][1] = 0
• ナップサックの大きさが2のときは、品物1を入れられるので価値が4、以降も同じ

(手順3) 品物2までを見ていく

• ナップサックの大きさが1のときは品物を入れられないので C[2][1] = 0
• ナップサックの大きさが2~5のときは、品物2を入れられる
  • C[2][4] では "C[1][2] + 品物2の価値(=4+5)" OR "C[1][4](=4)" のいずれか大きい方を選ぶ

(手順4) 品物3までを見ていく

• 品物1~3まで見ているので軽い重量でも入れられるようになった
• ナップサックの大きさが1~5のときは、品物1~3のどれかを入れられる

(手順5) 品物4までを見ていく

• 品物1~4まで見ている

ソースコードに落とし込む

手順に書いたとおり、品物の数を1~Nまで見ていくループの中で、重さを順に見ていく２重ループになるはず

• 疑似コード(AOJ版)

knapsack()

  for i = 1 to N
    for w = 1 to W
      if items[i].w <= w
        if items[i].v + C[i-1][w - items[i].w] > C[i-1][w]
          C[i][w] = items[i].v + C[i-1][w - items[i].w]
          G[i][w] = DIAGONAL // 品物 i を選ぶ
        else
          C[i][w] = C[i-1][w]
          G[i][w] = TOP
      else
        C[i][w] = C[i-1][w]
        G[i][w] = TOP        // 品物 i を選べない

• 漸化式(01ナップサック問題)
  • 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}

• 疑似コード(蟻本版)
  • items[i].v + C[i-1][w - items[i].w] > C[i-1][w] は、２値を与えてその大きい方をとる関数にまとめられる
  • あと G[][] の記録をしていない

knapsack()

  for i = 1 to N
    for w = 1 to W
      if items[i].w <= w
        C[i][w] = max(items[i].v + C[i-1][w - items[i].w], C[i-1][w])
      else
        C[i][w] = C[i-1][w]

• Rubyコード

# coding: utf-8
lines = <<'EOS'
4 5
4 2
5 2
2 1
8 3
EOS

#lines = $stdin.read
array = lines.split("\n")

def knapsack(n,w,items)

  dp = Array.new(N+1).map{Array.new(W+1, 0)}

  for i in 1...N+1
    for w in 1...W+1
      if items[i].w <= w
        dp[i][w] = [items[i].v + dp[i-1][w - items[i].w], dp[i-1][w]].max
      else
        dp[i][w] = dp[i-1][w]
      end
    end
  end

  dp
end

Item  = Struct.new(:v, :w)
N,W   = array[0].split(" ").map(&:to_i)

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

dp = knapsack(N,W,items)
puts dp.max.max

個数制限なしナップサック問題

問題

重さと価値がそれぞれ Wi, Vi であるようなN種類の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。 ただし、同じ種類の品物をいくつでも選ぶことができます

方針

同じ種類の品物をK個とるとすると、これは３重ループになり計算量が多すぎる → 漸化式を変形することで２重ループにまとめられる

ソースコードに落とし込む

数学ベースで漸化式を立てて、２重ループで実装する

• 漸化式(01ナップサック問題)
  • 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}

• 漸化式(個数制限なしナップサック問題) ... 式変形後
  • max(dp[i][j], dp[i+1][j-w[i]] + v[i])

• 疑似コード(独自)
  • 実際, C[i-1][w - items[i].w] が C[i][w - items[i].w] に変わっただけなのだ

knapsack()

  for i = 1 to N
    for w = 1 to W
      if items[i].w <= w
        C[i][w] = max(items[i].v + C[i][w - items[i].w], C[i-1][w])
      else
        C[i][w] = C[i-1][w]

• Rubyコード

# coding: utf-8
lines = <<'EOS'
4 5
4 2
5 2
2 1
8 3
EOS

#lines = $stdin.read
array = lines.split("\n")

def knapsack(n,w,items)

  dp = Array.new(N+1).map{Array.new(W+1, 0)}

  for i in 1...N+1
    for w in 1...W+1
      if items[i].w <= w
        dp[i][w] = [items[i].v + dp[i][w - items[i].w], dp[i-1][w]].max
      else
        dp[i][w] = dp[i-1][w]
      end
    end
  end

  dp
end

Item  = Struct.new(:v, :w)
N,W   = array[0].split(" ").map(&:to_i)

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

dp = knapsack(N,W,items)
puts dp.max.max

  01ナップサック問題 - 類題

• AOJ - Combinatorial - 0-1 Knapsack Problem
• AIZU ONLINE JUDGE 0042 「A Thief」

  個数制限なしナップサック問題 - 類題

• AOJ - Combinatorial - Knapsack Problem