ในปัญหานี้ เราได้รับจำนวนเต็ม n และเมทริกซ์ขนาด n X n ซึ่งมีน้ำหนักของเซลล์ งานของเราคือสร้างโปรแกรมที่จะค้นหาเส้นทางน้ำหนักสูงสุดที่สิ้นสุดที่องค์ประกอบใด ๆ ของแถวสุดท้ายในเมทริกซ์ ขณะค้นหาเส้นทาง การข้ามผ่านจะเริ่มต้นจากซ้ายบน (0,0) และการเคลื่อนไหวที่ถูกต้องจะลดลงและเป็นแนวทแยง ไม่อนุญาตให้เคลื่อนที่ไปทางซ้าย
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล −
n = 3
Mat[3][3] ={
{4, 3, 1}
{5, 8, 9}
{6, 7, 2}} ผลผลิต −
19
คำอธิบาย −
All paths that can be used will be Path1: 4+5+6 = 15 Path2: 4+8+7 = 19 Path3: 4+8+2 = 12 Path4: 4+5+7 = 16
จากนี้ไปเส้นทางที่ดีที่สุดคือ path2 ที่มีน้ำหนัก 19
ดังนั้น วิธีแก้ไขที่เป็นไปได้วิธีหนึ่งสามารถคำนวณเส้นทางทั้งหมดแล้วเปรียบเทียบได้ แต่จะเป็นวิธีที่ไม่มีประสิทธิภาพเมื่อมีจำนวนมาก
วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้โปรแกรมไดนามิกเนื่องจากเป็นประเภทของปัญหาที่ทับซ้อนกัน เริ่มต้นจากราก n กิ่งก้านที่สามารถให้ผลลัพธ์ที่ต้องการได้
เราจะสร้างเมทริกซ์ที่จะเก็บน้ำหนักสูงสุดของเส้นทางที่กำหนดซึ่งจะข้ามไปถึงเซลล์นั้นในเมทริกซ์
ซึ่งเราจะเป็นผลรวมสูงสุดในแถวสุดท้ายของเมทริกซ์แล้วพิมพ์ออกมา
ตัวอย่าง
โปรแกรมแก้ปัญหา
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
int maxCost(int matrix[][MAX], int N) {
int sumMat[N][N];
memset(sumMat, 0, sizeof(sumMat));
int maxSum = 0;
sumMat[0][0] = matrix[0][0];
for (int i=1; i<N; i++)
sumMat[i][0] = matrix[i][0] + sumMat[i-1][0];
for (int i=1; i<N; i++)
for (int j=1; j<i+1&&j<N; j++)
sumMat[i][j] = matrix[i][j] + max(sumMat[i-1][j-1], sumMat[i-1][j]);
for (int i=0; i<N; i++)
if (maxSum < sumMat[N-1][i]) maxSum = sumMat[N-1][i];
return maxSum;
}
int main(){
int mat[MAX][MAX] ={
{5 , 6 , 1 },
{2 , 11 , 10 },
{15, 3 , 2 }};
int N = 3;
cout<<"Maximum Path Sum for top-left cell to last row is : "<<maxCost(mat, N)<<endl;
return 0;
} ผลลัพธ์
Maximum Path Sum for top-left cell to last row is : 22
