Динамическое программирование.Матрица 4xn, как найти максимальную сумму в O (n)

Question

У меня мало ограничений.Я не могу выбрать значения из ячеек с общей стороной (диагональ в порядке).Я могу выбрать несколько элементов из каждого столбца.

Например.У меня есть матрица

1 3 6 10 3
4 2 6 7  9
5 1 8 3  3
9 2 9 1  1 

Если я выберу 1 и 5, сначала я должен выбрать 2 и 2 во вторую, 6 и 8 в третью и т. Д.

Лучше всего я могупридумать это грубое форсирование алгоритма, но это O (n ^ 4) какие-нибудь идеи?Я посмотрел на венгерский алгоритм, но он не работает и в O (n).

Спасибо!

Answer 1

Если матрица ограничена 4 × n, мы можем просто запустить динамическую программу.Предполагая, что наш выбор для любого столбца может быть только одним из:

a) x  b) -  c) -  d) -
   -     x     -     -
   -     -     x     -
   -     -     -     x

e) x  f) -  g) x  h) -
   -     x     -     -
   x     -     -     -
   -     x     x     -

Мы можем определить f(i, p), чтобы представить максимальную сумму вплоть до i-го столбца, когда мы выбираем шаблон p длянаш выбор элементов.Тогда:

f(i, a) = sum ith column elements pattern a + max(
  f(i - 1, b),
  f(i - 1, c),
  f(i - 1, d),
  f(i - 1, f),
  f(i - 1, h)
)

f(i, b) = sum ith column elements pattern b + max(
  f(i - 1, a),
  f(i - 1, c),
  f(i - 1, d),
  f(i - 1, e),
  f(i - 1, g),
  f(i - 1, h)
)

etc.

Поскольку p ограничен 8 вариантами выбора, пространство поиска равно O(n * 8) = O(n).