Задача на динамическое программирование Python

Question

Не могу решить задачу. Неправильно считает минимальный путь. Можете подсказать где ошибка? Вот условие задачи: В прямоугольной таблице N×M (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.

ifile = open('INPUT.txt')
outfile = open('OUTPUT.txt', 'w')
s = [int(i) for i in ifile.readline().split()]
n = s[0]#3
m = s[1]#4
price = []
c = [[0] * (m + 1) for i in range(n + 1)]


for i in range(1, n + 1):
    price.append([int(j) for j in ifile.readline().split()])


for i in range(1, n + 1):
    for j in range(1, m + 1):
        c[i][j] = price[i - 1][j - 1]

for i in price:
    print(i)

for i in range(1, n):
    for j in range(1, m):
        c[i][j] = min(c[i - 1][j], c[i][j - 1]) + c[i][j]

print(c[i][j])

input.txt:

В output.txt ответ

правильный ответ - 8 Помогите найти ошибку

Answer 1

Прежде всего не забывайте закрывать файлы после того, как они станут вам не нужны.

ifile.close()
outfile.close()

или же пользуйтесь следующей конструкцией:

with open(filename, permissions) as file_variable_name:
    ...
    # работа с файлом
    ...
...
# Дальнейшая работа
...

Открытый файл остается в системе в виде работающего процесса даже после закрытия программы.

Было бы неплохо, если бы вы обосновали идею вашего алгоритма, потому что подход к решению непонятен, но вам стоит проверить значение элементов списка c после конечных преобразований.

Взамен указания ошибки в вашей реализации, могу предложить иной подход к решению задачи:

Обратите внимание, что если в ваших исходных данных n+1 строк и m+1 столбцов, то для перехода из позиции 0,0 в позицию n,m вам необходимо сделать n-1 шагов вправо и m-1 шагов вниз.

Скажем, что True - это шаг вправо, а False - это шаг вниз. В вашем временном двумерном массиве будет C из n-1 по n+m-2 строк и n+m-2 столбцов, а каждая строка - это способ пройти по таблице, выраженный в последовательности True и False.

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

Примерная реализация:

from itertools import *

with open('INPUT.txt') as f:
    n, m = map(int, f.readline().split())
    price = [[int(i) for i in line.split()] for line in f]

whereToGo = [list(o) for o in set(permutations([True if i > n-2 else False for i in range(0,n+m-2)]))]


for i in range(len(whereToGo)):
    d,r = 0,0
    for j in range(len(whereToGo[i])):
        if whereToGo[i][j]:
            r += 1
        else:
            d += 1
        whereToGo[i][j] = price[d][r]
    whereToGo[i] = sum(whereToGo[i])

print(min(whereToGo) + price[0][0])

Протестировано только на вашем примере.

Answer 2

Введение нулевых ячеек сослужило плохую службу. Проще заполнить первую строку и столбец отдельно кумулятивными суммами, у вас это не получается из-за того, что вверху или слева ноль. Стоило при отладке посмотреть на c, чтобы это заметить

price = []
for i in range(n):
    price.append([int(j) for j in ifile.readline().split()])

for i in range(1, n):
    price[i][0] += price[i - 1][0]
for i in range(1, m):
    price[0][i] += price[0][i - 1]

for i in range(1, n):
    for j in range(1, m):
        price[i][j] = min(price[i - 1][j], price[i][j - 1]) + price[i][j]

print(price[-1][-1])

>> 8

БЛОГ НА HUSL

Задача на динамическое программирование Python

Ответы (2 шт):