पायथन प्रोग्राम: न्यूनतम लागत पथ

इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे।

समस्या कथन

हमें एक लागत मैट्रिक्स और एक स्थिति (m, n) दी गई है, हमें (0, 0) से (m, n) तक पहुंचने के लिए न्यूनतम लागत पथ की लागत ज्ञात करनी है। प्रत्येक सेल एक सेल से दूसरे सेल तक पार करने की लागत को दर्शाता है।

उदाहरण

# डायनामिक दृष्टिकोण
R = 3
C = 3
def minCost(cost, m, n):
    # इनिशियलाइज़ेशन
    tc = [[0 for x in range(C)] for x in range(R)]
    # आधार मामला
    tc[0][0] = cost[0][0]
    # कुल लागत (tc) सरणी
    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, 5, 3],
        [7, 7, 4],
        [8, 5, 3]]
print("Total Cost:", minCost(cost, 2, 1))

आउटपुट

Total Cost: 13

निष्कर्ष

इस लेख में हमने न्यूनतम लागत पथ के पायथन प्रोग्राम के बारे में सीखा।