【Ruby】【アルゴリズム】ナップザック問題。綺麗なコード。

　
師匠からメールが来たよ。

動的計画法もおさえておいたほうがいいですね

だって。

前にも解いたことあるけどね。

まあ、考えたうちに入らないっていうことかな。

ここを参考に。
最強最速アルゴリズマー養成講座：病みつきになる「動的計画法」、その深淵に迫る (1/4) - ITmedia エンタープライズ

改めて書くとコードがぜんぜん変ってびっくり。
　　

問題

幾つかの品物があり、この品物にはそれぞれ重量・価値の2つのパラメータが与えられています。ある一定の重さまで品物を運べるとしたときに、価値の合計の最大値は幾つになるでしょう？

ただし品物は1種類1個しかない。

コード全量

ITEM = {
a: [3, 2],
b: [4, 3],
c: [5, 7],
d: [6, 10],
e: [9, 14]
}
def solve(knapsack)
  ITEM.each do |_, info|
    proposed_cost, proposed_value = info[0], info[1]
    knapsack.size.times do |target_size|
      knapsack[proposed_cost] = proposed_value if knapsack[proposed_cost] < proposed_value
      next if knapsack[target_size + proposed_cost].nil?
      #値の存在するところだけ検査を行う
      next if knapsack[target_size] == 0  #<= （ア）
      candidate_value = knapsack[target_size] + proposed_value
      knapsack[target_size + proposed_cost] = [knapsack[target_size + proposed_cost], candidate_value].max
    end
  end
  knapsack.shift
  knapsack
end
def max_value_with_size(knapsack_size)
  solve(Array.new(knapsack_size+1, 0))
end
p max_value_with_size(20)
p max_value_with_size(20).max

　
■実行結果

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

　
ポイントは、maxメソッドで、配列内の最大値を取得すること。

（ア）の条件分岐を行っているため、
このアルゴリズムでは、例えばITEMが一個だけだった場合、

ITEM = {
a: [3, 2],
}

こんな風に、「サイズ３の価値は2、サイズ４の価値は0」と表現されてしまう。

[0, 0, 2, 0, 0, 4, 0, 0, 6, 0, 0, 8, 0, 0, 10, 0, 0, 12, 0, 0]

だから最大値を取ります。