ナップサック問題を動的計画法で解く

knapsack.rb

require 'delegate'
# https://github.com/tj/terminal-table
require 'terminal-table'

# ナップサック問題（Ruby）
# http://obelisk.hatenablog.com/entry/2017/05/26/162601
# 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
# https://qiita.com/drken/items/a5e6fe22863b7992efdb

class Item
  attr_reader :weight, :value

  def initialize(weight:, value:)
    @weight = weight
    @value = value
  end
end

class DpTable < DelegateClass(Array)
  attr_reader :row_size, :column_size, :table

  def initialize(row_size, column_size)
    @row_size = row_size
    @column_size = column_size
    @table = Array.new(row_size) { Array.new(column_size, 0) }

    super(@table)
  end

  def to_s
    Terminal::Table.new do |t|
      t.headings = [nil, *(0...column_size)]
      table.each_with_index do |row, i|
        t.add_row([i, *row])
      end
      t.style = { all_separators: true }
    end.to_s
  end
end

items = [[2, 3], [1, 2], [3, 6], [2, 1], [1, 3], [5, 85]].map { Item.new(weight: _1, value: _2) }
W = 9
N = items.size

# 行が個数、列が重量の表を用意する。
table = DpTable.new(N + 1, W + 1)

items.each_with_index do |item, i|
  (0..W).each do |weight|
    if weight >= item.weight
      # item を選ぶ場合: table[i][weight - item.weight] + item.value
      # item を選ばない場合: table[i][weight]
      table[i + 1][weight] = [table[i][weight - item.weight] + item.value, table[i][weight]].max
    else
      table[i + 1][weight] = table[i][weight]
    end

    puts("\e[H\e[2J") # clear
    puts('(重さ, 価値) = (' + items.map { "(#{_1.weight}, #{_1.value})" }.join(', ') + ')')
    puts
    puts(table.to_s)

    sleep(0.5)
  end
end

puts
puts("答: #{table[N][W]}")

(重さ, 価値) = ((2, 3), (1, 2), (3, 6), (2, 1), (1, 3), (5, 85))
+---+---+---+---+---+---+----+----+----+----+----+
|   | 0 | 1 | 2 | 3 | 4 | 5  | 6  | 7  | 8  | 9  |
+---+---+---+---+---+---+----+----+----+----+----+
| 0 | 0 | 0 | 0 | 0 | 0 | 0  | 0  | 0  | 0  | 0  |
+---+---+---+---+---+---+----+----+----+----+----+
| 1 | 0 | 0 | 3 | 3 | 3 | 3  | 3  | 3  | 3  | 3  |
+---+---+---+---+---+---+----+----+----+----+----+
| 2 | 0 | 2 | 3 | 5 | 5 | 5  | 5  | 5  | 5  | 5  |
+---+---+---+---+---+---+----+----+----+----+----+
| 3 | 0 | 2 | 3 | 6 | 8 | 9  | 11 | 11 | 11 | 11 |
+---+---+---+---+---+---+----+----+----+----+----+
| 4 | 0 | 2 | 3 | 6 | 8 | 9  | 11 | 11 | 12 | 12 |
+---+---+---+---+---+---+----+----+----+----+----+
| 5 | 0 | 3 | 5 | 6 | 9 | 11 | 12 | 14 | 14 | 15 |
+---+---+---+---+---+---+----+----+----+----+----+
| 6 | 0 | 3 | 5 | 6 | 9 | 85 | 88 | 90 | 91 | 94 |
+---+---+---+---+---+---+----+----+----+----+----+
答: 94