トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

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

[アルゴリズム,DP]

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

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

  問題設定

理解のために

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

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

指針

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

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

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

01ナップサック問題

問題
重さと価値がそれぞれ Wi, Vi であるようなN個の品物があります。これらの品物から、重さの総和がWを超えないように選んだときの、価値の総和の最大値を求めなさい。
方針
(1) 品物の価値と重さを記録する配列 (2) i番目までの品物を考慮して大きさwのナップサックに入れる場合の価値の合計の最大値をC[i][w]とする2次元配列を準備する
実際に解いてみる
items[N+1] 品物の価値と重さを記録 / C[N+1][W+1] i番目までの品物を考慮して大きさwのナップサックに入れる場合の価値の合計の最大値

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

v w 備考
4 2 品物1
5 2 品物2
2 1 品物3
8 3 品物4

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

    • ナップサックの大きさw=0のとき
    • 品物の数iが0個の場合
  • 二次元配列は C[N+1][W+1] ← C[品物の数+1][容量+1]
  • 縦軸は品物の個数、横軸は容量
0 0 0 0 0 0
0
0
0
0

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

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

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

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

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

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

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

  • 品物1~4まで見ている
0 0 0 0 0 0
0 0 4 4 4 4
0 0 5 5 9 9
0 2 5 7 9 11
0 2 5 8 10 13
ソースコードに落とし込む
手順に書いたとおり、品物の数を1~Nまで見ていくループの中で、重さを順に見ていく2重ループになるはず
  • 疑似コード(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%5Bi%2B1%5D%5Bj%5D+%3D+%5Cbegin%7Beqnarray%7D+%5Cleft%5C%7B+%5Cbegin%7Barray%7D%7Bl%7D+dp%5Bi%5D%5Bj%5D+%28j+%3C+w%5Bi%5D%29+%5C%5C+max%28dp%5Bi%5D%5Bj%5D%2C+dp%5Bi%5D%5Bj%2Dw%5Bi%5D%5D%2Bv%5Bi%5D%29+%5Cend%7Barray%7D+%5Cright%2E+%5Cend%7Beqnarray%7D+
  • 疑似コード(蟻本版)
    • items[i].v + C[i-1][w - items[i].w] > C[i-1][w] は、2値を与えてその大きい方をとる関数にまとめられる
    • あと 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個とるとすると、これは3重ループになり計算量が多すぎる → 漸化式を変形することで2重ループにまとめられる
ソースコードに落とし込む
数学ベースで漸化式を立てて、2重ループで実装する
  • 漸化式(01ナップサック問題)
    • dp%5Bi%2B1%5D%5Bj%5D+%3D+%5Cbegin%7Beqnarray%7D+%5Cleft%5C%7B+%5Cbegin%7Barray%7D%7Bl%7D+dp%5Bi%5D%5Bj%5D+%28j+%3C+w%5Bi%5D%29+%5C%5C+max%28dp%5Bi%5D%5Bj%5D%2C+dp%5Bi%5D%5Bj%2Dw%5Bi%5D%5D%2Bv%5Bi%5D%29+%5Cend%7Barray%7D+%5Cright%2E+%5Cend%7Beqnarray%7D+
  • 漸化式(個数制限なしナップサック問題) ... 式変形後
    • max%28dp%5Bi%5D%5Bj%5D%2C+dp%5Bi%2B1%5D%5Bj%2Dw%5Bi%5D%5D+%2B+v%5Bi%5D%29+
  • 疑似コード(独自)
    • 実際, 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ナップサック問題 - 類題

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

お名前: コメント: