C++ เส้นทางที่มีค่าเฉลี่ยสูงสุด (Path with Maximum Average Value)

ได้รับเมทริกซ์ 2 มิติ ในปัญหานี้ เราต้องหาเส้นทางที่มีค่าเฉลี่ยสูงสุด แหล่งที่มา (Source) คือเซลล์มุมซ้ายบน และปลายทาง (Destination) คือเซลล์มุมขวาล่าง เช่น

Input : Matrix = [1, 2, 3; 4, 5, 6; 7, 8, 9] Output : 5.8
เส้นทางที่มีค่าเฉลี่ยสูงสุดคือ 1 -> 4 -> 7 -> 8 -> 9
ผลรวมของเส้นทางคือ 29 และค่าเฉลี่ยคือ 29/5 = 5.8

ในปัญหานี้ เราได้รับอนุญาตให้เคลื่อนที่ไปขวาหรือลงเท่านั้น ซึ่งทำให้ปัญหาง่ายขึ้น เพราะเรารู้ว่าต้องเคลื่อนที่ขวา N-1 ครั้ง และลง N-1 ครั้ง เพื่อไปถึงปลายทาง นี่คือเส้นทางสั้นที่สุดที่ถูกต้อง เราจะพัฒนาวิธีแก้จากข้อสังเกตเหล่านี้

วิธีการแก้ปัญหา

ในวิธีนี้ เราต้องใช้ Dynamic Programming เพื่อคำนวณ Maximum Path Sum เนื่องจากตัวส่วน (จำนวนขั้นตอน) เป็นค่าคงที่

ตัวอย่าง

โค้ด C++ สำหรับวิธีการข้างต้น

#include <bits/stdc++.h> 
using namespace std; 

int maximumPathSum(int cost[][3], int n){ 
    int dp[n+1][n+1]; 
    dp[0][0] = cost[0][0]; 
    for (int i = 1; i < n; i++) 
        dp[i][0] = dp[i-1][0] + cost[i][0]; 
    for (int j = 1; j < n; j++) 
        dp[0][j] = dp[0][j-1] + cost[0][j]; 
    for (int i = 1; i < n; i++) 
        for (int j = 1; j <= n; j++) 
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + cost[i][j]; 
    return dp[n-1][n-1]; 
} 

int main(){ 
    int cost[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; 
    int n = 3; 
    printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1))); 
    return 0; 
}

ผลลัพธ์

5.8

คำอธิบายโค้ด

ในวิธีนี้ เราสังเกตว่าจำนวนขั้นตอนสูงสุดที่เราเดินเท่ากับ (2*n) - 1 โดย n คือขนาดเมทริกซ์ ตอนนี้ตัวส่วนเป็นค่าคงที่แล้ว เราจึงต้องคำนวณ Maximum Path Sum ซึ่งเป็นปัญหา DP คลาสสิก เราแก้ด้วย DP แล้วพิมพ์ผลลัพธ์

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาการหา Path with maximum average value เรายังได้เรียนรู้โปรแกรม C++ และวิธีแก้ปัญหา ซึ่งสามารถเขียนในภาษาอื่น เช่น C, Java, Python ได้ หวังว่าจะเป็นประโยชน์