এই সমস্যায়, আমাদের 2 x n আকারের একটি আয়তক্ষেত্রাকার গ্রিড দেওয়া হয়েছে। আমাদের কাজ হল 2 x n গ্রিডে সর্বাধিক যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা যাতে C++ এ দুটি উপাদান সংলগ্ন না থাকে।
সমস্যা বর্ণনা
সর্বাধিক যোগফল খুঁজে পেতে, আমরা বর্তমান উপাদানের সংলগ্ন উপাদানগুলি নির্বাচন করতে পারি না, উল্লম্বভাবে, অনুভূমিকভাবে বা তির্যকভাবে৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
rectGrid[2][] =389 411
আউটপুট
13
ব্যাখ্যা
সমস্ত সম্ভাব্য যোগফল হল
যদি আমরা rectGrid[0][0] অর্থাৎ 3 থেকে শুরু করি, তাহলে আমরা শুধুমাত্র 9 বা 1 যোগ করতে পারি। সর্বোচ্চ যোগফল হল 12।
যদি আমরা rectGrid[1][0] অর্থাৎ 4 থেকে শুরু করি, তাহলে আমরা শুধুমাত্র 9 বা 1 যোগ করতে পারি। সর্বোচ্চ যোগফল হল 13।
যদি আমরা rectGrid[0][1] অর্থাৎ 8 থেকে শুরু করি, তাহলে আমরা কোনো উপাদান যোগ করতে পারব না। সর্বাধিক যোগফল 8।
যদি আমরা rectGrid[1][1] অর্থাৎ 1 থেকে শুরু করি, তাহলে আমরা কোনো উপাদান যোগ করতে পারব না। সর্বাধিক যোগফল হল 1।
যদি আমরা rectGrid[0][2] অর্থাৎ 9 থেকে শুরু করি, তাহলে আমরা শুধুমাত্র 3 বা 4 যোগ করতে পারি। সর্বোচ্চ যোগফল হল 13।
যদি আমরা rectGrid[1][2] অর্থাৎ 1 থেকে শুরু করি, তাহলে আমরা শুধুমাত্র 3 বা 4 যোগ করতে পারি। সর্বোচ্চ যোগফল হল 5।
সামগ্রিক সর্বোচ্চ যোগফল 13।
সমাধান পদ্ধতি
সমস্যাটি সর্বাধিক যোগফলের অনুরূপ যে কোনও দুটি উপাদান সংলগ্ন নয় যা আমরা শেষ পোস্টে দেখেছি। পার্থক্য হল অ্যারে যা এখানে 2D এবং সন্নিহিত উপাদানগুলির শর্ত। সুতরাং, আমরা সারি এবং কলাম উভয়ের শর্ত ব্যবহার করে সর্বাধিক উপাদান বিবেচনা করব। যেহেতু প্রতিটি কলামে দুটি সারি রয়েছে, তাই আমরা বিকল্প উপাদানগুলির সর্বাধিক সম্ভাব্য বিবেচনা করব৷
উদাহরণ
সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include<iostream>
using namespace std;
int findMax(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSum(int rectGrid[2][20], int N){
int currectSum = 0;
int nextSum = 0;
int altSum;
for (int i = 0; i<N; i++ ){
altSum = findMax(nextSum, currectSum);
currectSum = nextSum + findMax(rectGrid[0][i], rectGrid[1][i]);
nextSum = altSum;
}
int maxSum = findMax(nextSum, currectSum);
return maxSum;
}
int main(){
int rectGrid[2][20] = {{3, 8, 9, 5},
{4, 1, 2, 7}};
int N = 4;
cout<<"The maximum sum in a 2 x "<<N<<" grid such that no two elements are adjacent is "<<calcMaxSum(rectGrid, N);
return 0;
} আউটপুট
The maximum sum in a 2 x 4 grid such that no two elements are adjacent is 15
