MaxMyInterest knapsack interview problem

input.txt

$15.05
mixed fruit,$2.15
french fries,$2.75
side salad,$3.35
hot wings,$3.55
mozzarella sticks,$4.20
sampler plate,$5.80

lib.rb

require 'set'
ValidMenuLineItems = Struct.new(:currency__target, :price__target, :arr__arr__MenuLineItem__valid, :arr__arr__count__MenuLineItem__valid)
MenuItem = Struct.new(:name, :currency, :price)
MenuLineItem = Struct.new(:name, :currency, :price, :count, :subtotal)
=begin
= puts_valid_menu_line_items
= Example usage
  See the bottom of this file for example usage.
  The contents of input.txt are passed to a new instance of FactoryValidMenuItems & the #call return value is formatted
=end
def puts_valid_menu_line_items(txt_input)
  currency__target, price__target, arr__arr__MenuLineItem__valid = *FactoryValidMenuItems.new(txt_input).call
  if arr__arr__MenuLineItem__valid && !arr__arr__MenuLineItem__valid.empty?
    printf "The following menu combinations match the target price of #{currency__target}%.2f\n", price__target
    arr__arr__MenuLineItem__valid.each_with_index do |arr__MenuLineItem__valid, i|
      puts "\tCombination #{i + 1}"
      arr__MenuLineItem__valid.each do |__MenuLineItem__valid|
        name, currency, price, count, subtotal = *__MenuLineItem__valid
        next if count == 0
        printf "\t\t%-20s %8s\n", "#{count} #{name}", sprintf("#{currency}%.2f", subtotal)
      end
    end
  else
    printf "No combination of dishes will be equal in cost to the target price of #{currency__target}%.2f\n", price__target
  end
end
class FactoryValidMenuItems
  attr_accessor :txt__input
  attr_reader :currency__target, :price__target, :arr__MenuItem
  def initialize(txt__input)
    @txt__input = txt__input
    @set__arr__count__MenuItem__valid = Set.new
  end
  def call
    set__arr__count__MenuItem__valid.clear
    @currency__target, @price__target, @arr__MenuItem = _arr__input
    arr__arr__MenuLineItem__valid = _arr__arr__MenuLineItem__valid
    arr__arr__count__MenuLineItem__valid = arr__arr__MenuLineItem__valid.map do |arr__MenuLineItem__valid|
      arr__MenuLineItem__valid.map(&:count)
    end
    ValidMenuLineItems.new(currency__target, price__target, arr__arr__MenuLineItem__valid, arr__arr__count__MenuLineItem__valid)
  end
  protected

  attr_reader :set__arr__count__MenuItem__valid
  def _cents(price)
    (price * 100).to_i
  end
  def cents__total
    _cents(price__target)
  end
  def _arr__input
    arr__txt__input = txt__input.split("\n")
    currency__target, price__target = _arr__currency__price(arr__txt__input[0])
    arr__MenuItem = arr__txt__input[1..-1].map do |input|
      arr__input = input.split(',')
      MenuItem.new(arr__input[0], *_arr__currency__price(arr__input[1]))
    end
    [currency__target, price__target, arr__MenuItem]
  end
  def _arr__arr__MenuLineItem__valid()
    arr__count__MenuItem__zero = Array.new(arr__MenuItem.length)
    arr__MenuItem.each_with_index do |root_MenuItem, i|
      name, currency, price = *root_MenuItem
      cents = _cents(price)
      max_count__MenuItem__root = (cents__total / cents).to_i
      max_count__MenuItem__root.downto(0) do |count__MenuItem__root|
        arr__count__MenuItem__root = _arr__count__MenuItem__copy(arr__count__MenuItem__zero, i, count__MenuItem__root)
        add__set__arr__count__MenuItem__valid(arr__count__MenuItem__root)
      end
    end
    set__arr__count__MenuItem__valid.to_a.map do |arr__count__MenuItem__valid|
      arr__count__MenuItem__valid.each_with_index.map do |count, i|
        name, currency, price = *arr__MenuItem[i]
        subtotal = (_cents(price) * count) / 100.0
        MenuLineItem.new(name, currency, price, count, subtotal)
      end
    end
  end
  def add__set__arr__count__MenuItem__valid(arr__count__MenuItem)
    cents__arr__count__MenuItem = _cents__arr__count__MenuItem(arr__count__MenuItem)
    if cents__total == cents__arr__count__MenuItem
      arr__count__MenuItem = _arr__count__MenuItem__copy__replace__null__with__0(arr__count__MenuItem)
      set__arr__count__MenuItem__valid.add(arr__count__MenuItem)
    end
    return if cents__arr__count__MenuItem >= cents__total
    cents__remaining = cents__total - cents__arr__count__MenuItem
    arr__MenuItem.each_with_index do |__MenuItem, i|
      next unless arr__count__MenuItem[i].nil? # traversed
      cents__MenuItem = _cents(arr__MenuItem[i].price)
      max_count__MenuItem__remaining = (cents__remaining / cents__MenuItem).to_i
      max_count__MenuItem__remaining.downto(0) do |count__MenuItem|
        arr__count__MenuItem = _arr__count__MenuItem__copy(arr__count__MenuItem, i, count__MenuItem)
        add__set__arr__count__MenuItem__valid(arr__count__MenuItem) if count__MenuItem > 0
      end
    end
  end
  def _arr__count__MenuItem__copy(arr__count__MenuItem, i, count)
    arr__count__MenuItem__copy = arr__count__MenuItem.dup
    arr__count__MenuItem__copy[i] = count
    arr__count__MenuItem__copy
  end
  def _arr__count__MenuItem__copy__replace__null__with__0(arr__count__MenuItem)
    arr__count__MenuItem.map do |count, i|
      count || 0
    end
  end
  def _arr__currency__price(txt__price)
    match = /(\W*)([0-9\.]*)/.match(txt__price)
    [match[1], match[2].to_f]
  end
  def _cents__arr__count__MenuItem(arr__count__MenuItem)
    cents__arr__count__MenuItem = 0
    arr__MenuItem.each_with_index do |__MenuItem, i|
      cents = _cents(__MenuItem.price)
      count = arr__count__MenuItem[i] || 0
      cents__arr__count__MenuItem += (cents * count)
    end
    cents__arr__count__MenuItem
  end
end

if __FILE__ == $0
  puts_valid_menu_line_items(File.read('./input.txt'))
  puts_valid_menu_line_items('$20.00')
end