ナップザック問題 入っているアイテムの種類が出力できない

Question

Rubyでナップザック問題のコードをかいて入っているアイテムの種類を出力しようとしたら上手くいかなかった

下の記事を参考にしてRubyでナップザックに入っているアイテムを出力しようとしたのですが、ナップザックに入っているのかをうまく判定できていないようです。

参考にさせていただいた記事
https://qiita.com/fukumone/items/19f13c143dd006fbb1aa

require "time"

@all_times = []
@selected_items = []
N = 4
ARRAY = [[2, 3], [1, 2], [3, 4], [2, 2]]
ARRAY_W = [2, 1, 3, 2]
ARRAY_V = [3, 2, 4, 2]
W = 5

def rec(i, j)
  t1 = Time.now
  res = 0
  if i == N
    # もう品物は残っていない
    res = 0
  elsif j < ARRAY_W[i]
    #この品物は入らない
    res = rec(i + 1, j)
  else
    #入れない場合と入れる場合の両方を試す
    if rec(i + 1, j) < rec(i + 1, j - ARRAY_W[i]) + ARRAY_V[i]
      in_the_knap = true
      res = rec(i + 1, j - ARRAY_W[i]) + ARRAY_V[i]
    else
      in_the_knap = false
      res = rec(i + 1, j)
    end
    if in_the_knap == true
      now_item = [ARRAY_W[i], ARRAY_V[i]]
      @selected_items.push(now_item)
    end
  end
  t2 = Time.now
  @all_times.push(t2 - t1)
  res
end

puts "rec : #{rec(0, W)}"
p @all_times.sum.round(4)
@selected_items.uniq!
p :selected_items, @selected_items

# 出力
rec : 7
0.0004
:selected_items
[[2, 2], [3, 4], [2, 3]]

"in_the_knap"でナップザックに入ったかを判定しているつもりです...

Answer 1

rec関数は、rec(i + 1, j)とrec(i + 1, j - ARRAY_W[i])の2回呼び出されますが、
その戻り値のうち実際に採用されるのは、大きい値を返した方だけです。
つまり、採用されない側の呼び出しで選ばれた要素は追加してはいけないということです。

しかし、今のコードだと、現在の要素については採用されたかを判定していますが、
採用されない側のrecの再帰呼び出しの中ですでに@selected_itemsに追加されてしまったものについては
削除されずにそのまま残るため、余計な要素まで結果として表示されてしまうことになります。

採用されたかどうか知っているのは呼び出し元だけなので、入れたアイテムを戻り値として返して、
呼び出し元で採用していない側を捨てるぐらいしか方法はないと思われます。

アイテムと価値合計を両方返すと、戻り値を分離して各々処理しなければならず大変なので、
アイテムだけ返して価値合計は都度計算という形に書き換えると、このような感じでしょうか。
(都度計算のため遅くなりますが)

#再帰呼び出し

N = 4
ARRAY = [ [2, 3], [1, 2], [3, 4], [2, 2] ]
ARRAY_W = [ 2, 1, 3, 2 ]
ARRAY_V = [ 3, 2, 4, 2 ]
W = 5

def rec(i, j)
  if i == N
    # もう品物は残っていない
    res = []
  elsif j < ARRAY_W[i]
    #この品物は入らない
    res = rec(i + 1, j)
  else
    #入れない場合と入れる場合の両方を試す
    res = [ rec(i + 1, j), [[ARRAY_W[i], ARRAY_V[i]]] + rec(i + 1, j - ARRAY_W[i]) ].max{|a,b| a.sum{|e|e[1]} <=> b.sum{|e|e[1]}}
  end
  res
end

puts "#{rec(0, W)}"