gistfile1.rb

#!/usr/bin/ruby                                                                                                                               
                                                                                                                                              
def bottom_up(p, n)                                                                                                                           
  r = Array.new(n,0)                                                                                                                          
  (1..n).each do |j|                                                                                                                          
    q = -1                                                                                                                                    
    (1..j).each do |i|                                                                                                                        
      q = [q, r[j-i] + p[i]].max                                                                                                              
    end                                                                                                                                       
    r[j] = q                                                                                                                                  
  end                                                                                                                                         
  return r[n];                                                                                                                                
end                                                                                                                                           
                                                                                                                                              
profit = {0=>0,1=>1,2=>5,3=>4,4=>8}                                                                                                           
                                                                                                                                              
puts bottom_up(profit,3)