Динамическое программирование с Ruby

Вам не разрешено создавать два магазина, которые находятся на расстоянии менее чем в k милях друг от друга. Проблема проста: как максимизировать свою прибыль?

Святая корова, это кажется действительно сложным. Вы должны как-то манипулировать между требованием расстояния и магазинами с самой высокой прибылью. Оказывается, мы можем использовать динамическое программирование, чтобы получить решение этой проблемы!

Давайте определим функцию (в математическом смысле) T где представляет максимальную прибыль, если вы должны были просто закончить список магазинов на расстоянии х . Таким образом, ценность, которую мы ищем в конце дня где n — количество магазинов.

Прежде всего, обратите внимание, что максимальная прибыль неизменна для расстояний между магазинами. Например, если у нас есть магазин в 10, а другой в 20:

Теперь давайте попробуем разобраться с большей проблемой вычислений в некоторые меньшие проблемы. Скажем, мы хотим максимизировать прибыль на расстоянии для некоторых я . Тогда мы можем включить все магазины, которые находятся k единиц «позади»

Итак, мы можем написать:

Кроме того, если мы заканчиваем дистанцию ​​прямо в первом магазине, то максимальная прибыль — это прибыль, которую может получить первый магазин. По математике:

Теперь, когда у нас есть математическая идея алгоритма DP, давайте закодируем его в Ruby:

 def T(x, m, t_hash)
  return 0 if x < m[0]

  keys = t_hash.keys.sort
  relative_distances = keys.map do |d|
    x - d
  end

  #filter out the stores to leave only the
  #ones that come atleast "k" units before "x"
  filtered_distances = relative_distances.select do |r|
    r >= 0
  end

  key = keys[filtered_distances.index filtered_distances.min]
  return t_hash[key]
end

def dept_store(m, p, k)
  t_hash = {m[0] => p[0]}

  (1..m.length-1).to_a.each do |j|
    b = m[j] - k
    t_hash[m[j]] = p[j] + T(b, m, t_hash)
  end

  p t_hash
  t_hash.values.max
end

Давайте посмотрим на реализацию первый:

 def T(x, m, t_hash)
  return 0 if x < m[0]

  keys = t_hash.keys.sort
  relative_distances = keys.map do |d|
    x - d
  end

  #filter out the stores to leave only the
  #ones that come atleast "k" units before "x"
  filtered_distances = relative_distances.select do |r|
    r >= 0
  end

  key = keys[filtered_distances.index filtered_distances.min]
  return t_hash[key]
end

Основная проблема заключается в том, чтобы убедиться, что если у нас есть значение x между двумя магазинами, то возвращается прибыль для магазина с меньшим расстоянием. Чтобы сделать это, код вычисляет расстояния каждого магазина от x , отфильтровывает магазины, которые находятся перед x, и затем выбирает тот, который ближе всего. То, как это происходит, немного неуклюже, но выполняет свою работу.

Обратите внимание, что t_hash например, t_hash[m[i]]

Но только расположение магазинов — это ключи в t_hash

Теперь, когда у нас есть Tдействительно проста:

 def dept_store(m, p, k)
  t_hash = {m[0] => p[0]}

  (1..m.length-1).to_a.each do |j|
    b = m[j] - k
    t_hash[m[j]] = p[j] + T(b, m, t_hash)
  end

  t_hash.values.max
end

Сначала мы начинаем, зная, что и мы добавляем эту информацию в t_hash Затем мы просто применяем соотношение несколько раз. В конце мы просто возвращаем максимальную прибыль, которую мы можем получить!

Взять домой очки:

• Мы разбили сложную проблему на более простые, более мелкие проблемы
• Мы использовали функцию для отслеживания состояния (фактически, мы неявно сделали то же самое для более раннего примера; бонусные баллы, если вы можете определить функцию!)
• Мы создали отношения, которые позволили нам «выстроить» решение нашей большой проблемы
• Наше решение работает в линейном времени
• Тот же трюк с делением проблемы «на основании того, где они заканчиваются» был использован довольно эффективно

Это все люди!

Надеемся, что эта статья дала вам представление о концепциях динамического программирования.
а также некоторые идеи о том, как реализовать их в Ruby.