इस समस्या में, हमें एक पूर्णांक 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
इनमें से सबसे अच्छा संभव पथ पथ 2 है जिसका वजन 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