এই সমস্যায়, আমাদের একটি অ্যারে দেওয়া হয়েছে arr[]। আমাদের কাজ হল সর্বাধিক যোগফল খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা যাতে C++ এ দুটি উপাদান সংলগ্ন না থাকে।
সমস্যা বর্ণনা
আমাদের অ্যারে থেকে ক্রমটির সর্বাধিক যোগফল খুঁজে বের করতে হবে যাতে যোগফলের ক্রম থেকে কোনও 2 সংখ্যা অ্যারের সংলগ্ন না হয়৷
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {5, 1, 3, 7, 9, 2, 5} আউটপুট
22
ব্যাখ্যা
Taking sum sequence from index 0 with alternate elements : 5 + 3 + 9 + 5 = 22 Taking sum sequence from index 1 with alternate elements : 1 + 7 + 2 = 10
সমাধান পদ্ধতি
শেষ সেটে, আমরা সমস্যা সমাধানের জন্য একটি পদ্ধতি দেখেছি। এখানে, আমরা সমস্যা সমাধানের জন্য গতিশীল প্রোগ্রামিং পদ্ধতি সম্পর্কে শিখব।
ডায়নামিক অ্যাপ্রোচ ব্যবহার করে সমস্যা সমাধানের জন্য, আমাদের একটি DP[] অ্যারে তৈরি করতে হবে যা বর্তমান সূচক পর্যন্ত সর্বাধিক সমষ্টি সংরক্ষণ করে। এবং তারপর এই গতিশীল অ্যারে ব্যবহার করে যোগফল সূচক খুঁজুন।
বর্তমান DP সর্বোচ্চ হল dp[i+2]+ arr[i] এবং dp[i+1] এর সর্বোচ্চ।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int DP[100];
bool currState[100];
int maxVal(int a, int b){
if(a > b)
return a;
return b;
}
int calcMaxSumWOAdj(int arr[], int i, int n){
if (i >= n)
return 0;
if (currState[i])
return DP[i];
currState[i] = 1;
DP[i] = maxVal(calcMaxSumWOAdj(arr, i + 1, n), arr[i] + calcMaxSumWOAdj(arr, i + 2, n));
return DP[i];
}
int main(){
int arr[] = { 5, 1, 3, 7, 9, 2, 5 };
int n = sizeof(arr) / sizeof(int);
cout<<"The maximum sum such that no two elements are adjacent is "<<calcMaxSumWOAdj(arr, 0, n);
return 0;
} আউটপুট
The maximum sum such that no two elements are adjacent is 22
