Pebbling Шахматная доска с динамическим программированием

Question

Я пытаюсь научить себя динамическому программированию и столкнулся с этой проблемой от MIT.

Нам дана шахматная доска, которая имеет 4 строки и n столбцов, а имеет целое число, записанное на каждом квадрате. Нам также дают набор из 2n гальки, и мы хотим разместить некоторые или все из них на шахматной доске (каждая галька может быть размещена ровно на один квадрат) , чтобы максимизировать сумму целых чисел в квадратах, которые покрытый галькой. Существует одно ограничение: для размещения гальки должно быть законным, никакие два из них не могут быть горизонтально или вертикально смежных квадратов (диагональная смежность в порядке).

(a) Определите количество юридических шаблонов, которые могут возникать в любом столбце (изолированно, игнорируя гальки в соседних столбцах) и описывайте эти шаблоны. Вызовите два шаблона совместимыми, если их можно разместить на соседних столбцах, чтобы сформировать юридическое размещение. Рассмотрим подзадачи, состоящие из первых k столбцов 1 k n. Каждой подзадаче может быть присвоен тип , который является шаблоном, имеющим место в последнем столбце.

(b) Используя понятия совместимости и типа, дайте алгоритм динамического программирования O (n) -time для вычисления оптимального размещения.

Хорошо, поэтому для части a: существует 8 возможных решений.

Для части b, я не уверен, но это - то, куда я направляюсь: SPlit в под-проблемы. Предположим, что i в n. 1. Определите Cj [i] как оптимальное значение, делясь столбцами 0, ..., i, так что столбец i имеет тип шаблона j. 2. Создайте 8 отдельных массивов из n элементов для каждого типа шаблона.

Я не уверен, куда идти отсюда. Я понимаю, что есть решения этой проблемы в Интернете, но решения мне кажутся не очень ясными.

Answer 1

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

Допустим, вы создали свой список совместимости (2D-массив) и назвал его L _я [у], что для каждого шаблона я есть один или несколько совместимых моделей L _я [у ].

Теперь вы изучите колонку j. Сначала вы вычисляете изолированные оценки столбца для каждого шаблона i. Звоните S _j [i]. Для каждого шаблона я и совместимо шаблон х = L _я [у], необходимо максимизировать общий балл C _J таким образом, что С _J [х] = С _{J- 1} [i] + S _j [x]. Это простой тест массива и обновление (если оно больше).

Кроме того, вы храните шаблон гальки, который привел к каждому результату. При обновлении C _J [х] (т.е. вы увеличить свой счет от ее текущей стоимости), то помните, начальные и последующие образцы, которые вызвали обновление, как P _J [х] = я. Это говорит о том, что «шаблон x дал лучший результат, учитывая предыдущий шаблон i».

Когда вы все сделали, просто найти шаблон я с лучшей оценкой C _п [я]. Затем вы можете вернуться с помощью P _j, чтобы восстановить шаблон гальки из каждого столбца, который привел к такому результату.