Shows whether a knapsack problem is solvable or unsolvable.

knapsack.rb

menu_1 = [1, 2.50, 3.50]
target_1 = 450

menu_2 = [0.31]
target_2 = 450

menu_3 = [2.15, 2.75, 3.35, 3.55, 4.20, 5.80, 6.55]
target_3 = 15.05

def knapsack(menu, target, current_price)
  puts "menu = #{ menu }, target = #{ target }, current_price = " + 
       "#{ current_price }, diff = #{ current_price - target }"
  if current_price == target
    return true
  elsif current_price > target
    return false
  else
    menu.each do |i|
      solution_exists = knapsack(menu, target, current_price + i)
        if solution_exists
          return true 
        end
    end
    return false
  end
end

puts knapsack(menu_1,target_1,0)
puts knapsack(menu_2,target_2,0)
puts knapsack(menu_3,target_3,0)