ナップザック

dp.rb

# frozen_string_literal: true
# require 'pry-byebug'

def check_path(goods, n, w, table, acc=[])
  # p [:acc, n, w, acc]
  # binding.pry
  if n == 0
    acc
  else
    if table[n][w] == table[n - 1][w]
      # 一つ前までの商品の合計価値と、いまの商品も含めた合計価値が同じなら
      # 今の商品(goods[n-1])は選択されなかったことになる
      check_path(goods, n - 1, w, table, acc)
    else
      # 選択されたので、accに商品追加
      check_path(goods, n - 1, w - goods[n - 1][0], table, acc + [goods[n - 1]])
    end
  end
end

def dp(n, w, goods)
  d = Array.new(n + 1) do
    Array.new(w + 1, 0)
  end

  1.upto(n) do |i|
    # p goods[i - 1]
    0.upto(w) do |j|
      if j >= goods[i - 1][0]
        d[i][j] = [
          d[i - 1][j - goods[i - 1][0]] + goods[i - 1][1],
          d[i - 1][j],
        ].max
      else
        d[i][j] = d[i - 1][j]
      end
    end
  end
  # テーブルダンプ
  # puts d.map { |row| row.map { |e| format("%3d", e) }.join }.join("\n")

  # テーブルをもとに選んだ商品を表示
  p check_path(goods, n, w, d)

  d[n][w]
end

# (weight, value)
goods = [[2, 3], [1, 2], [3, 6], [2, 1], [1, 3], [5, 85]]
weight = 8
puts goods.map{|e| e.inspect}.join(', ')
puts dp(goods.size, weight, goods)