読者です 読者をやめる 読者になる 読者になる

せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】ナップザック問題、解説がおかしい・・・?(わけではなかった)

 
(注)以下の問題は、
「品物はそれぞれひとつずつ」の条件があります。
その制約を見落としていたので、以下のように
「解説が間違えてるの?」と勘違いしてしまいました。
解説は間違えていませんでした!ごめんなさい。。(10月11日13時追記)

 
昨日解いたコードは
解説されているアルゴリズムに沿っていないので、ふたたび考え直し。 
最強最速アルゴリズマー養成講座:病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ


 
解説のアルゴリズムはこう。
f:id:sekaiya:20131011081823j:plain

 

アイテムを順々に見ていくのだけど、アイテムの重さ時点にアイテムを入れた場合、
その重さ×n(>=2)のサイズの箇所は更新していない

具体的にいうと、
2番目のアイテムを入れるときに、
サイズ4・サイズ7は更新するけど、サイズ8(2番目のアイテムが2つ分入るところ)は更新しない
f:id:sekaiya:20131011082713j:plain

 
でもさ?これまずくない?
再帰的に値を入れていかないと、任意のナップサックの値に対応できないと思うんだけど。

実際問題、
「品物すべてについて試したもの」はこう書いてる↓
f:id:sekaiya:20131011082900j:plain

明らかに、例えば「ナップサックのサイズが100のとき」の最大値はサイズ13の時の値と同じになるよね。
(この表にはサイズ13は書いてないけど、上から赤線が延びるマックスの場所だよ)
 
 
コードを書いてみても、

ITEM = {
a: [3, 2],
b: [4, 3],
c: [1, 2],
d: [2, 3],
e: [3, 6]
}
def solve(knapsack)
  ITEM.each do |key, info|
    proposed_cost, proposed_value = info[0], info[1]
    next_knapsack = knapsack.dup
    knapsack.size.times do |target_size|
      if target_size == proposed_cost
        next_knapsack[proposed_cost] = [knapsack[proposed_cost], proposed_value].max
      end
      next if knapsack[target_size] == 0
      next if knapsack[target_size + proposed_cost].nil?
      candidate_value = knapsack[target_size] + proposed_value
      next_knapsack[target_size + proposed_cost] = [knapsack[target_size + proposed_cost], candidate_value].max
    end
    p knapsack = next_knapsack
  end
  knapsack
end
def max_value_with_size(knapsack_size)
  solve(Array.new(knapsack_size+1, 0))
end
answer = max_value_with_size(20)
p answer.max

  
■実行結果

[0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 2, 3, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 2, 4, 5, 0, 5, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 3, 5, 4, 5, 7, 8, 7, 8, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 3, 6, 8, 9, 11, 10, 11, 13, 14, 13, 14, 16, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 3, 6, 8, 9, 11, 10, 11, 13, 14, 13, 14, 16, 0, 0, 0, 0, 0, 0, 0]
16

サイズが大きいところはぜんぜん詰まってないのが分かるよね。

この解説は、あくまで小さいサイズのときの「概念」かな?
 
そもそも、サイズ2のときって、
アイテムCを2個つめるのが一番最大価値なんだから、
この表自体間違えてると思うんだけど?
f:id:sekaiya:20131011083518j:plain

 
正しくはこうじゃないかな?

ITEM = {
a: [3, 2],
b: [4, 3],
c: [1, 2],
d: [2, 3],
e: [3, 6]
}
def solve(knapsack)
  ITEM.each do |key, info|
    proposed_cost, proposed_value = info[0], info[1]
    knapsack[proposed_cost] = [knapsack[proposed_cost], proposed_value].max
    knapsack.size.times do |target_size|
      next if knapsack[target_size] == 0  #<= (ア)
      next if knapsack[target_size + proposed_cost].nil?
      candidate_value = knapsack[target_size] + proposed_value
      knapsack[target_size + proposed_cost] = [knapsack[target_size + proposed_cost], candidate_value].max
    end
  end
  knapsack
end
def max_value_with_size(knapsack_size)
  solve(Array.new(knapsack_size+1, 0))
end
answer = max_value_with_size(20)
p answer
p answer.max

 
■実行結果

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]
40


アイテムを変えてやってみても正しく回答できてる。

ITEM = {
a: [3, 2],
b: [4, 3],
c: [5, 7],
d: [6, 10],
e: [9, 14]
}

■実行結果

[0, 0, 0, 2, 3, 7, 10, 5, 9, 14, 14, 17, 20, 17, 21, 24, 24, 27, 30, 28, 31]
31


どうなんだろう?

いってきます。