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

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

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

　
解説のアルゴリズムはこう。

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

具体的にいうと、
2番目のアイテムを入れるときに、
サイズ4・サイズ7は更新するけど、サイズ8（2番目のアイテムが2つ分入るところ）は更新しない

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

実際問題、
「品物すべてについて試したもの」はこう書いてる↓

明らかに、例えば「ナップサックのサイズが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

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

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

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

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

どうなんだろう？

いってきます。