सी++ में त्रिभुज में अधिकतम पथ योग

इस समस्या में, हमें ऐसी संख्याएँ दी जाती हैं जो एक त्रिभुज के रूप में होती हैं। हमारा काम एक ऐसा प्रोग्राम बनाना है जो एक त्रिभुज में अधिकतम पथ योग प्राप्त करे।

तत्वों को पहली पंक्ति से 1 एक तत्व के साथ व्यवस्थित किया जाता है और फिर अगली पंक्तियों में तत्वों की बढ़ती संख्या के साथ nth पंक्ति में तत्व होने तक व्यवस्थित किया जाता है।

तो, कार्यक्रम उस पथ को खोजेगा जो त्रिभुज में तत्वों की अधिकतम राशि प्रदान करेगा। इसलिए, हमें वह रास्ता खोजना होगा जो अधिकतम राशि प्रदान करे।

आइए समस्या को समझने के लिए एक उदाहरण लेते हैं -

इनपुट -

  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