knapsack.rb

def knapsack(weights, values, max_weight)
  raise ArgumentError nil if weights.length != values.length
  matrix = (1..values.length).collect { || Array.new(max_weight + 1, 0) }
  matrix.each_with_index do |row, i|
    weight = weights[i]
    value  = values[i]
    row.each_with_index do |current_value, j|
      previous = matrix[i - 1][j].to_i
      if j >= weight
        row[j] = new = [matrix[i - 1][j - weight].to_i + value, previous].max
      else
        row[j] = previous
      end
    end
  end
  picked(weights, matrix)
end

def picked(weights, matrix)
  i = matrix.length - 1
  j = matrix.first.length - 1
  picks = []
  while j >= 0 && i >= 0
    if matrix[i - 1][j].to_i < matrix[i][j].to_i
      picks << i
      j -= weights[i]
    end
    i -= 1
  end
  picks
end