Knapsack

gistfile1.txt

w = [10, 20, 30]
b = [60, 100, 120]

$result = {}
def knaspask(w, b, n, max_w)

  if n == 0 || max_w == 0
    result = 0
  else
    if result = $result["#{n.to_s}-#{max_w.to_s}"]
          return result
    end
    if w[n-1] > max_w
      result = knaspask(w, b, n-1, max_w)
    else
      result = [knaspask(w, b, n-1, max_w), b[n-1] + knaspask(w, b, n-1, max_w-w[n-1])].max
    end
  end
  $result["#{n},#{max_w}"] = result
  result
end

puts "RESULT #{knaspask(w, b, 3, 50)}"