ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาตามที่ระบุด้านล่าง
คำชี้แจงปัญหา − เราได้รับเมทริกซ์ต้นทุนและตำแหน่ง (m, n) เราจำเป็นต้องค้นหาต้นทุนของเส้นทางต้นทุนขั้นต่ำที่จะไปถึง (m, n) จาก (0, 0) แต่ละเซลล์แสดงถึงต้นทุนในการสำรวจจากเซลล์หนึ่งไปยังอีกเซลล์หนึ่ง
ทีนี้มาดูวิธีแก้ปัญหาในการใช้งานด้านล่างกัน −
ตัวอย่าง
# 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 สำหรับเส้นทางต้นทุนต่ำสุด
