Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में मैट्रिक्स में अंतिम पंक्ति के किसी भी एलिमेंट पर समाप्त होने वाला अधिकतम वजन पथ


इस समस्या में, हमें एक इंटीजर n और n X n आकार का एक मैट्रिक्स दिया गया है जिसमें सेल का वजन होता है। हमारा कार्य एक ऐसा प्रोग्राम बनाना है जो मैट्रिक्स में अंतिम पंक्ति के किसी भी एलिमेंट पर समाप्त होने वाले अधिकतम वजन पथ को ढूंढे। पथ ढूंढते समय ट्रैवर्सल टॉप-लेफ्ट (0,0) से शुरू होगा और वैध चालें नीचे और विकर्ण होंगी, कोई बाईं चाल अनुमति नहीं है।

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

इनपुट −

n = 3 Mat[3][3] ={    {4, 3, 1}    {5, 8, 9}    {6, 7, 2}}

आउटपुट  −

19

व्याख्या −

उपयोग किए जा सकने वाले सभी पथ होंगे पथ1: 4+5+6 = 15 पथ2: 4+8+7 = 19 पथ3: 4+8+2 = 12 पथ4: 4+5+7 = 16

इनमें से सर्वोत्तम संभव पथ पथ2 है जिसका वजन 19 है

तो, एक संभावित समाधान सभी पथों की गणना करना और फिर उनकी तुलना करना हो सकता है, लेकिन जब n बड़ी संख्या हो तो यह दृष्टिकोण अक्षम होगा।

एक प्रभावी समाधान डायनामिक प्रोग्रामिंग का उपयोग करना होगा क्योंकि यह एक ओवरलैपिंग समस्या का प्रकार है। रूट से शुरू होकर 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

  1. - मैट्रिक्स के किसी भी कॉलम में अधिकतम अंतर वाली जोड़ी खोजें C++ में

    मान लीजिए हमारे पास NxN क्रम का एक मैट्रिक्स है। हमें तत्वों की एक जोड़ी खोजनी है जो मैट्रिक्स के किसी भी कॉलम से अधिकतम अंतर बनाती है। तो यदि मैट्रिक्स इस तरह है - 123 535 967 तो आउटपुट 8 होगा। क्योंकि जोड़ी (1, 9) कॉलम 0 से है। विचार सरल है, हमें बस प्रत्येक कॉलम के अधिकतम और न्यूनतम तत्वों के

  1. - C++ प्रोग्राम: मैट्रिक्स की प्रत्येक पंक्ति का अधिकतम तत्व ज्ञात करना

    मान लें हमारे पास एक मैट्रिक्स है, हमारा कार्य उस मैट्रिक्स की प्रत्येक पंक्ति का अधिकतम तत्व ज्ञात करना और उन्हें प्रिंट करना है। यह कार्य सरल है। प्रत्येक पंक्ति के लिए, मैक्स को रीसेट करें, और अधिकतम तत्व ज्ञात करें, और इसे प्रिंट करें। आइए बेहतर समझ के लिए कोड देखते हैं। उदाहरण #include <ios

  1. - C++ प्रोग्राम: मैट्रिक्स के प्रत्येक कॉलम का अधिकतम तत्व ज्ञात करना

    मान लें हमारे पास एक मैट्रिक्स है, हमारा कार्य उस मैट्रिक्स के प्रत्येक कॉलम का अधिकतम तत्व ज्ञात करना और उन्हें प्रिंट करना है। यह कार्य सरल है। प्रत्येक कॉलम के लिए, मैक्स को रीसेट करें, और अधिकतम तत्व ज्ञात करें, और इसे प्रिंट करें। आइए बेहतर समझ के लिए कोड देखते हैं। उदाहरण #include <iostrea