1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| Items = Struct.new(:day, :fee)
Settings = Struct.new(:rows, :max_day)
def zeros(rows, cols)
Array.new(rows) do |row|
Array.new(cols, 0)
end
end
def op_main(settings)
num_rows = settings.rows.size
rows = settings.rows
max_day = settings.max_day
day_matrix = zeros(num_rows, max_day+1)
num_rows.times do |i|
(max_day + 1).times do |j|
if(rows[i].day > j)
day_matrix[i][j] = day_matrix[i-1][j]
else
day_matrix[i][j] = [day_matrix[i-1][j], rows[i].fee + day_matrix[i-1][j-rows[i].day]].max
end
end
end
day_matrix
end
if $0 == __FILE__
rows = [
Items.new(9 , 130) , Items.new(12 , 150) ,
Items.new(20 , 190) , Items.new(23 , 190) ,
Items.new(27 , 230) , Items.new(33 , 290) ,
Items.new(31 , 330) , Items.new(9 , 70) ,
Items.new(30 , 330) , Items.new(9 , 110) ,
Items.new(6 , 90) , Items.new(34 , 310) ,
Items.new(34 , 330) , Items.new(22 , 190) ,
Items.new(25 , 230) , Items.new(13 , 170)
]
settings = Settings.new(rows, 100)
day_matrix = op_main settings
puts 'fee: ' + day_matrix.last.last.to_s
end |
Partager