এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা 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
এইগুলির মধ্যে সর্বোত্তম সম্ভাব্য পথ হল path2 যার ওজন 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
