ในปัญหานี้ เราได้รับตัวเลขที่อยู่ในรูปสามเหลี่ยม งานของเราคือสร้างโปรแกรมที่จะหาผลรวมเส้นทางสูงสุดในรูปสามเหลี่ยม
องค์ประกอบจะถูกจัดเรียงโดยเริ่มจากแถวที่ 1 โดยมีองค์ประกอบ 1 รายการ จากนั้นจึงจัดเรียงองค์ประกอบในแถวถัดไปโดยมีจำนวนองค์ประกอบเพิ่มขึ้นจนมีองค์ประกอบอยู่ในแถวที่ n
ดังนั้นโปรแกรมจะค้นหาเส้นทางที่จะให้ผลรวมสูงสุดขององค์ประกอบในรูปสามเหลี่ยม เราจึงต้องหาเส้นทางที่จะให้ผลรวมสูงสุด
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน −
ป้อนข้อมูล −
1 5 6 8 2 9
ผลผลิต − 16
คำอธิบาย −
เส้นทางจากด้านบนจะคืนค่าผลรวมสูงสุด − 9+6+1 =16
เพื่อแก้ปัญหานี้ เราจะใช้โปรแกรมไดนามิกที่จะใช้วิธีจากล่างขึ้นบน
สำหรับสิ่งนี้ อันดับแรก ให้เลื่อนตัวเลขทั้งหมดของสามเหลี่ยมไปทางซ้ายก่อน แล้วบวก 0 ต่อท้าย สิ่งนี้จะทำให้สามเหลี่ยมดูเหมือนเมทริกซ์ที่คล้ายกับที่เราเห็นในปัญหาเส้นทางต้นทุนขั้นต่ำ หลังจากนี้ เราจะเริ่มจากด้านล่าง และสำหรับแต่ละองค์ประกอบ เราจะตรวจสอบเส้นทางที่เป็นไปได้ทั้งหมด และเลือกเส้นทางที่ให้ผลรวมสูงสุดที่เป็นไปได้จนถึงองค์ประกอบนั้น และข้ามไปด้านบนในลักษณะเดียวกันเพื่อหาผลรวมสูงสุดของเส้นทางในรูปสามเหลี่ยม
ตัวอย่าง
โปรแกรมหาผลรวมเส้นทางสูงสุดในรูปสามเหลี่ยม −
#include<iostream>
using namespace std;
#define N 3
int findMaxPathSumTriangle(int mat[][N], int m, int n){
for (int i=m-1; i>=0; i--){
for (int j=0; j<=i; j++){
if (mat[i+1][j] > mat[i+1][j+1])
mat[i][j] += mat[i+1][j];
else
mat[i][j] += mat[i+1][j+1];
}
}
return mat[0][0];
}
int main() {
int triangle[N][N] = {
{1, 0, 0},
{5, 6, 0},
{8, 2, 9} };
cout<<"The maximum path sum in triangle is "<<findMaxPathSumTriangle(triangle, 2, 2);
return 0;
} ผลลัพธ์
The maximum path sum in triangle is 16
