Максимально прибыльный путь

Question

Условие:

В зоне, расположенной в северо-западном углу, находится робот. Из зоны с координатами [i, j], 1≤ i ≤ n, 1 ≤ j ≤ m, робот может добыть не более ai,j граммов золота. По технологическим соображениям, на участке существуют ограничения: на каждом шаге робот может перемещаться из текущей зоны только в одну из соседних зон восточнее или южнее.

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

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

x = []

def calculate_path(matrix, line, column):
i = 0
j = 0
end = matrix[-1][-1]

while matrix[i][j] != end:
    if matrix[i][j] == matrix[-1][-1]:
        break
    if i == 0 and j == 0:
        x.append(matrix[i][j])
    if i >= line - 1:
        x.append(matrix[i][j + 1])
        j += 1
        continue
    if j >= column - 1:
        x.append(matrix[i + 1][j])
        i += 1
        continue
    if matrix[i + 1][j] > matrix[i][j + 1]:
        x.append(matrix[i + 1][j])
        i += 1
    elif matrix[i][j + 1] > matrix[i + 1][j]:
        x.append(matrix[i][j + 1])
        j += 1
return print(x)

calculate_path(matrix, int(len(matrix)), int(len(matrix[0])))

Пример матрицы:

matrix = [[1, 2, 3, 4, 5],
          [3, 4, 6, 5, 6],
          [6, 2, 7, 7, 5],
          [7, 2, 3, 4, 5]]

Для неё ответ должен быть таким: 1 => 3 => 4 => 6 => 7 => 7 => 5 => 5 сумма: 38

А в моей программе ответ такой: 1 => 3 => 6 => 7 => 2 => 3 => 4 => 5 сумма: 31

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

Answer 1

Ваш алгоритм - "жадный", он не даёт оптимального решения в общем случае.

А вот метод динамического программирования - даст оптимум. При его использовании для каждой ячейки определяется, откуда в неё выгоднее прийти - сверху или слева.

if (dp[i-1][j] > dp[i][j-1]) {
    dp[i][j] = dp[i-1][j] + matrix[i][j];
    и запомнить направление сверху
    }
else {
    dp[i][j] = dp[i][j-1] + matrix[i][j];
    и запомнить направление слева
    }

Левый столбец и верхнюю строку можно заполнить предварительно.

  matrix = [[1, 2, 3, 4, 5],
          [3, 4, 6, 5, 6],
          [6, 2, 7, 7, 5],
          [7, 2, 3, 4, 5]]


dp = [[0]*5 for i in range(len(matrix))]

s = [[""]*5 for i in range(len(matrix))]

s[0][0] = str(matrix[0][0])
for j in range(len(matrix[0])):
    dp[0][j] = dp[0][j - 1] + matrix[0][j]
    s[0][j] = s[0][j-1] + " " + str(matrix[0][j])
for i in range(1, len(matrix)):
    dp[i][0] = dp[i-1][0] + matrix[i][0]
    s[i][0] = s[i-1][0] + " " + str(matrix[i][0])

for i in range(1, len(matrix)):
    for j in range(1, len(matrix[0])):
        if dp[i - 1][j] > dp[i][j - 1]:
            dp[i][j] = dp[i - 1][j] + matrix[i][j]
            s[i][j] = s[i-1][j] + " " + str(matrix[i][j])
        else:
            dp[i][j] = dp[i][j - 1] + matrix[i][j]
            s[i][j] = s[i][j-1] + " " + str(matrix[i][j])
print(dp[3][4]);
print(s[3][4])

38
1 3 4 6 7 7 5 5

БЛОГ НА HUSL

Максимально прибыльный путь

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