তিনটি অ্যারে থেকে সর্বাধিক যোগফল যেমন C++ এ একই থেকে ধারাবাহিকভাবে উপাদান বাছাই করা অনুমোদিত নয়

এই সমস্যায়, আমাদেরকে তিনটি অ্যারে দেওয়া হয়েছে arr1[], arr2[], এবং arr3[] সমস্ত N আকারের। আমাদের কাজ হল তিনটি অ্যারে থেকে সর্বোচ্চ যোগফল বের করার জন্য একটি প্রোগ্রাম তৈরি করা যাতে একই থেকে ধারাবাহিকভাবে উপাদান বাছাই করা হয় না। C++ এ অনুমোদিত।

সমস্যা বর্ণনা

আমরা N উপাদান নির্বাচন করে সর্বাধিক যোগফল খুঁজে বের করব। i=th উপাদানটি অ্যারের i-th উপাদান থেকে যোগফল নির্বাচন করা যেতে পারে অর্থাৎ ith যোগফল arr1[i]/ arr2[i]/ arr3[i] থেকে। এছাড়াও, মনে রাখবেন যে আমরা একই অ্যারে থেকে বেছে নেওয়া যেতে পারে এমন দুটি পরপর উপাদান নির্বাচন করতে পারি না।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

ইনআউট

arr1[] = {5, 8, 9, 20},
arr2[] = {7, 12, 1, 10},
arr3[] = {8, 9, 10, 11}
N = 4

আউটপুট

50

ব্যাখ্যা

i =1 এর জন্য, আমরা arr3 থেকে যোগফলের জন্য 8 বিবেচনা করব। i =2 এর জন্য, আমরা arr2 থেকে যোগফলের জন্য 12 বিবেচনা করব। i =3 এর জন্য, আমরা arr3 থেকে যোগফলের জন্য 10 বিবেচনা করব। i =4 এর জন্য, আমরা arr1 থেকে যোগফলের জন্য 20 বিবেচনা করব। যোগফল =8 + 12 + 10 + 20 =50

সমাধান পদ্ধতি

সমস্যা সমাধানের জন্য, আমরা গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করব, অতিরিক্ত গণনা এড়াতে আমাদের সূচক পর্যন্ত যোগফল মুখস্ত করতে হবে। আমরা একটি 2-ডি ম্যাট্রিক্স তৈরি করব, DP[][]। সূচী i,j-এ উপাদানটি হবে i-th সূচক এবং j-th অ্যারে ব্যবহার করা পর্যন্ত উপাদানগুলির সমষ্টি। আমরা পুনরাবৃত্তভাবে বর্তমানের জন্য উপাদানগুলি খুঁজে বের করব এবং তারপরে অন্য দুটি অ্যারে থেকে পরবর্তী উপাদানগুলির যোগফলকে কল করব৷

উদাহরণ

আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,

#include <bits/stdc++.h>
using namespace std;
const int N = 3;
int findMaxVal(int a, int b){
   if(a > b)
      return a;
      return b;
}
int FindMaximumSum(int index, int arrNo, int arr1[], int arr2[], int arr3[], int n, int DP[][N]){
   if (index == n)
      return 0;
   if (DP[index][arrNo] != -1)
      return DP[index][arrNo];
      int maxVal = -1;
   if (arrNo == 0){
      maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
      maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
   }
   else if (arrNo == 1){
      maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
      maxVal = findMaxVal(maxVal, arr3[index] + FindMaximumSum(index + 1, 2, arr1, arr2, arr3, n, DP));
   }
   else if (arrNo == 2){
      maxVal = findMaxVal(maxVal, arr1[index] + FindMaximumSum(index + 1, 1, arr1, arr2, arr3, n, DP));
      maxVal = findMaxVal(maxVal, arr2[index] + FindMaximumSum(index + 1, 0, arr1, arr2, arr3, n, DP));
   }
   return DP[index][arrNo] = maxVal;
}
int main(){
   int arr1[] = { 5, 8, 9, 20 };
   int arr2[] = { 7, 12, 1, 10 };
   int arr3[] = { 8, 9, 10, 11 };
   int n = sizeof(arr1) / sizeof(arr1[0]);
   int DP[n][N];
   memset(DP, -1, sizeof DP);
   int val1 = FindMaximumSum(0, 0, arr1, arr2, arr3, n, DP);
   int val2 = FindMaximumSum(0, 1, arr1, arr2, arr3, n, DP);
   int val3 = FindMaximumSum(0, 2, arr1, arr2, arr3, n, DP);
   cout<<"The maximum sum from three arrays such that picking elements consecutively from same is not allowed is "<<findMaxVal(val1, findMaxVal(val2, val3));
   return 0;
}

আউটপুট

The maximum sum from three arrays such that picking elements consecutively from same is not allowed is 50