the knapsack problem

knapsack.rb

class Item
  attr_accessor :name, :weight, :price
end
  
class Knapsack
  attr_accessor :items, :capacity, :table

  def initialize(capacity)
    @items = []
    @capacity = capacity
    @table = Hash.new([0, [nil]])
  end

  def fill_items
    return "No available items" if items.empty?
    items.each_with_index do |item, index|
      row = index + 1
      (1..capacity).each do |column|
        previous_max_value = table[[row-1, column]][0]
        previous_max_name = table[[row-1, column]][1]
        if column < item.weight
          table[[row, column]] = table[[row-1, column]]
        elsif column == item.weight
          new_value = item.price
          new_value >= previous_max_value \
            ? table[[row, column]] = [new_value, [item.name]] \
            : table[[row, column]] = [previous_max_value, previous_max_name]
        else
          diff_weight = column - item.weight
          diff_item_name = table[[row-1, diff_weight]][1]
          diff_item_value = table[[row-1, diff_weight]][0]
          new_value = item.price + diff_item_value
          if diff_item_value == 0
            table[[row, column]] = [new_value, [item.name]]
          else
            table[[row, column]] = [new_value, diff_item_name + [item.name]]
          end
        end
      end
    end
  end

  def find_best_combinations
    sorted_table = table.sort_by { |k, v| v[0] } # return an array
    max_combination_price = sorted_table[-1][1][0]
    p best_combinations = table.select { |k, v| v[0] == max_combination_price }
  end

end


guitar = Item.new; guitar.weight = 1; guitar.price = 1500; guitar.name = "guitar"
laptop = Item.new; laptop.weight = 3; laptop.price = 2000; laptop.name = "laptop"
stereo = Item.new; stereo.weight = 4; stereo.price = 3000; stereo.name = "stereo"
headphone = Item.new; headphone.weight = 2; headphone.price = 500; headphone.name = "headphone"
necklace = Item.new; necklace.weight = 1; necklace.price = 2500; necklace.name = "necklace"


knapsack = Knapsack.new(4)
knapsack.items = [stereo,laptop,guitar,headphone,necklace].shuffle
knapsack.fill_items
knapsack.find_best_combinations