knapsack-bt.rb

#!/usr/bin/env ruby
#
# knapsack problem solution by backtracking.
#
# from:
#   Cプログラマのためのアルゴリズムとデータ構造
#   ISBN:4797304952
#   pp. 348
#   
# author:
#   mootoh@gmail.com
#
require 'pp'

$stuffs = [ # [size, value]
  [2,  2],
  [3,  4],
  [5,  7],
  [7, 11],
  [9, 14]]

$values = {}

def knapsack_bt(m, stuffs, sofar)
  stuffs.each do |stuff|
    if stuff.first > m
      sum = 0
      sofar.each {|s| sum += $stuffs.find {|x| x.first == s}.last}
      $values[sofar.map {|so| $stuffs.map {|s| s.first}.index(so) }] = sum
      next
    end
    knapsack_bt(m - stuff.first, stuffs, sofar+[stuff.first])
  end
end

def knapsack(m)
  stuffs = $stuffs.sort { |x, y| x.first <=> y.first }.reverse
  results = []

  knapsack_bt(m, stuffs, [])

  pp $values

  print 'result: '
  pp $values.sort {|x,y| x[1] <=> y[1]}.last
end