Рубрики

Программа Python для Min Cost Path

Динамическое программирование, Программы Python

Учитывая стоимость матрицы затрат [] [] и позицию (m, n) в стоимости [] [], напишите функцию, которая возвращает стоимость пути минимальной стоимости для достижения (m, n) из (0, 0). Каждая ячейка матрицы представляет собой стоимость прохождения через эту ячейку. Общая стоимость пути для достижения (m, n) представляет собой сумму всех затрат на этом пути (включая как источник, так и пункт назначения). Вы можете перемещаться только вниз, вправо и по диагонали к нижним ячейкам из данной ячейки, то есть из данной ячейки (i, j), ячеек (i + 1, j), (i, j + 1) и (i + 1, j + 1) можно пройти. Вы можете предположить, что все затраты являются положительными целыми числами.

Например, как показано на следующем рисунке, какова минимальная стоимость пути к (2, 2)?

Путь с минимальной стоимостью выделен на следующем рисунке. Путь (0, 0) -> (0, 1) -> (1, 2) -> (2, 2). Стоимость пути составляет 8 (1 + 2 + 2 + 3).

# Динамическое программирование Python-реализация Min Cost Path
# проблема

R = 3

C = 3

  

def minCost(cost, m, n):

  

    # Вместо следующей строки мы можем использовать int tc [m + 1] [n + 1] или

    # динамически размещать памятки для экономии места. Следующее

    # строка используется для упрощения работы программы и обеспечения ее работоспособности

    # на всех компиляторах.

    tc = [[0 for x in range(C)] for x in range(R)]

  

    tc[0][0] = cost[0][0]

  

    # Инициализировать первый столбец массива общей стоимости (тс)

    for i in range(1, m + 1):

        tc[i][0] = tc[i-1][0] + cost[i][0]

  

    # Инициализировать первую строку массива tc

    for j in range(1, n + 1):

        tc[0][j] = tc[0][j-1] + cost[0][j]

  

    # Построить остаток массива tc

    for i in range(1, m + 1):

        for j in range(1, n + 1):

            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j],

                            tc[i][j-1]) + cost[i][j]

  

    return tc[m][n]

  
# Драйверная программа для проверки вышеуказанных функций

cost = [[1, 2, 3],

        [4, 8, 2],

        [1, 5, 3]]

print(minCost(cost, 2, 2))

  
# Этот код предоставлен Bhavya Jain

Выход:

8

Пожалуйста, обратитесь к полной статье о динамическом программировании | Установите 6 (Min Cost Path) для более подробной информации!

Рекомендуемые посты:

Программа Python для Min Cost Path

0.00 (0%) 0 votes