최소 비용 경로를 위한 Python 프로그램

이 기사에서는 아래 주어진 문제 설명에 대한 솔루션에 대해 알아볼 것입니다.

문제 설명 − 비용 행렬과 위치(m, n)가 주어지면 (0, 0)에서 (m, n)에 도달하는 최소 비용 경로의 비용을 찾아야 합니다. 각 셀은 한 셀에서 다른 셀로 이동하는 데 드는 비용을 나타냅니다.

이제 아래 구현에서 솔루션을 관찰해 보겠습니다 -

예시

# dynamic approach
R = 3
C = 3
def minCost(cost, m, n):
   # initialization
   tc = [[0 for x in range(C)] for x in range(R)]
   # base case
   tc[0][0] = cost[0][0]
   # total cost(tc) array
   for i in range(1, m + 1):
      tc[i][0] = tc[i-1][0] + cost[i][0]
   # tc array
   for j in range(1, n + 1):
      tc[0][j] = tc[0][j-1] + cost[0][j]
   # rest tc array
   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]
# main
cost = [[1, 5, 3],
        [7, 7, 4],
        [8, 5, 3]]
print("Total Cost:",minCost(cost, 2, 1))

출력

Total Cost: 13

모든 변수는 로컬 범위에서 선언되며 해당 참조는 위 그림과 같습니다.

결론

이 기사에서는 최소 비용 경로를 위한 Python 프로그램을 만드는 방법에 대해 배웠습니다.