Find jewels to transfer

find_jewels.rb

require "pp"

unless ARGV.size == 1
  $stderr.puts <<EOS
# ----------------------------------
# usage : ruby solve.rb input.dat
# ----------------------------------
EOS
  raise "Invalid argument"
end


class Stone
  
  @value
  @weight
  @density  # = value / weight

  attr_reader :value, :weight, :density

  def initialize( value, weight)
    @value = value
    @weight = weight
    @density = value.to_f / weight.to_f
  end
end

class NaiveSolver
  
  @stones
  @sorted_by_density
  @sorted_by_value
  @max_value
  # @max_value[x] : max value where total mass = x.
  #                 nil when a combination of stones whose total mass is x is not found
  attr_reader :stones, :sorted_by_density, :sorted_by_value
  
  def initialize( stones)
    @stones = stones
    @sorted_by_value = @stones.sort_by { |x| x.value }
    @sorted_by_density = @stones.sort_by { |x| x.density }
    @val_max = []
  end

  public
  def calc_val_max_upto( weight)

    for w in  @val_max.size..weight

      # find a stone whose weight is w
      found = @stones.find_all { |s| s.weight == w }
      @val_max[w] = found.max_by { |s| s.value }.value if found.size > 0      

      # find a combination
      for i in 1..(w/2)
        if @val_max[i] and @val_max[w-i]
          v = @val_max[i] + @val_max[w-i]
          @val_max[w] = v if v > @val_max[w].to_i
        end
      end
    end

    return @val_max
  end
end


# load file
stones = []
File.open(ARGV[0]).each do |line|
  arr = line.split.map { |x| x.to_i }
  stones << Stone.new( arr[0], arr[1])
end

pp stones
solver = NaiveSolver.new( stones)
solver.calc_val_max_upto(100).each_with_index do |val,idx| pp [idx,val] end