Путешественник по сетке: найдите максимальный балл, удовлетворяя ограничению, используя динамическое программирование. ⇐ Python
-
Anonymous
Путешественник по сетке: найдите максимальный балл, удовлетворяя ограничению, используя динамическое программирование.
Предположим, у нас есть сетка 9 x 9 с целочисленными значениями в каждой ячейке. Путешественник начинает с любого столбца по своему усмотрению в первой строке. Каждый ход он идет либо вниз, либо вниз-влево, либо вниз-вправо. То есть, если (i, j) — его текущая позиция, он может выбрать (i+1, j-1), (i+1, j), (i+ 1, j+1). Он продолжает, пока не дойдет до последнего ряда. На каждом шаге он добавляет к своему счету значение ячейки, в которую перешел.
Наша задача — найти максимально возможный балл, который он может получить, удовлетворяя следующему ограничению: он не может перейти в ячейку, если его балл плюс значение такой ячейки отрицательны. Например, в случае 3x3
1 2 3 3 4 -4 -2 2 4 Если он начинает с первой строки 3, он не может перейти к ячейке -4, потому что 3 - 4 < 0.
Рекурсивное решение в Python выглядит следующим образом:
импортировать numpy как np BOARD = [[random.randint(-9, 9) для _ в диапазоне (9)] для _ в диапазоне (9)] def traveller_rec(i, j, s): n = len(BOARD[1]) если j < 0 или j >= n: возврат (np.NINF) if i != 0 и s + BOARD[j] < 0: # Игроку разрешено начинать с ячейки с отрицательным значением возврат (np.NINF) если я == n - 1: return(BOARD[j]), если BOARD[j] > 0, иначе np.NINF вернуть максимум( BOARD[j] + traveller_rec(i + 1, j, s + BOARD[j]), BOARD[j] + traveller_rec(i + 1, j + 1, s + BOARD[j]), BOARD[j] + traveller_rec(i + 1, j - 1, s + BOARD[j]) ) Например, traveller_rec(0, 5, 0) дает максимально возможную оценку, начиная с индекса столбца 5.
Однако мне не удалось реализовать динамическое решение. Меня особенно интересует использование табуляции (а не запоминания) для такого решения. Как можно решить эту проблему с помощью динамического программирования?
Предположим, у нас есть сетка 9 x 9 с целочисленными значениями в каждой ячейке. Путешественник начинает с любого столбца по своему усмотрению в первой строке. Каждый ход он идет либо вниз, либо вниз-влево, либо вниз-вправо. То есть, если (i, j) — его текущая позиция, он может выбрать (i+1, j-1), (i+1, j), (i+ 1, j+1). Он продолжает, пока не дойдет до последнего ряда. На каждом шаге он добавляет к своему счету значение ячейки, в которую перешел.
Наша задача — найти максимально возможный балл, который он может получить, удовлетворяя следующему ограничению: он не может перейти в ячейку, если его балл плюс значение такой ячейки отрицательны. Например, в случае 3x3
1 2 3 3 4 -4 -2 2 4 Если он начинает с первой строки 3, он не может перейти к ячейке -4, потому что 3 - 4 < 0.
Рекурсивное решение в Python выглядит следующим образом:
импортировать numpy как np BOARD = [[random.randint(-9, 9) для _ в диапазоне (9)] для _ в диапазоне (9)] def traveller_rec(i, j, s): n = len(BOARD[1]) если j < 0 или j >= n: возврат (np.NINF) if i != 0 и s + BOARD[j] < 0: # Игроку разрешено начинать с ячейки с отрицательным значением возврат (np.NINF) если я == n - 1: return(BOARD[j]), если BOARD[j] > 0, иначе np.NINF вернуть максимум( BOARD[j] + traveller_rec(i + 1, j, s + BOARD[j]), BOARD[j] + traveller_rec(i + 1, j + 1, s + BOARD[j]), BOARD[j] + traveller_rec(i + 1, j - 1, s + BOARD[j]) ) Например, traveller_rec(0, 5, 0) дает максимально возможную оценку, начиная с индекса столбца 5.
Однако мне не удалось реализовать динамическое решение. Меня особенно интересует использование табуляции (а не запоминания) для такого решения. Как можно решить эту проблему с помощью динамического программирования?
