C++-এ তিনটি অ্যারে থেকে সর্বোচ্চ যোগফল যাতে একটি অ্যারে থেকে বারবার উপাদান নেওয়া যায় না

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

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

আমরা N টি উপাদান বেছে নিয়ে সর্বোচ্চ যোগফল বের করব। i-তম যোগফলের জন্য i-তম উপাদান যেকোনো একটি অ্যারে থেকে নেওয়া যাবে (arr1[i] বা arr2[i] বা arr3[i])। কিন্তু দুটি সমsekutিভ উপাদান একই অ্যারে থেকে নেওয়া যাবে না।

উদাহরণ

ইনপুট

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

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

এই সমস্যা সমাধান করতে ডাইনামিক প্রোগ্রামিং এবং মেমোইজেশন (memorization) ব্যবহার করা হবে। আমরা একটি 2D ম্যাট্রিক্স DP[][] তৈরি করব। DP[i][j] হবে i-তম ইনডেক্স পর্যন্ত এবং j-তম অ্যারে ব্যবহার করে পাওয়া যোগফল। রিকার্সিভভাবে বর্তমান উপাদান বেছে নেওয়া হয় এবং পরবর্তী উপাদান অন্য দুটি অ্যারে থেকে বেছে নেওয়া হয়।

প্রোগ্রাম উদাহরণ

#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