इस समस्या में, हमें संख्याएँ त्रिभुज के रूप में दी गई हैं। हमारा कार्य एक प्रोग्राम बनाना है जो त्रिभुज में अधिकतम पथ योग ढूंढेगा।
तत्वों को पहली पंक्ति से 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
