ধরুন আমাদের কাছে m এবং n আকারের ধনাত্মক পূর্ণসংখ্যার দুটি অ্যারে আছে। m> n. দ্বিতীয় অ্যারেতে শূন্য ঢোকানোর মাধ্যমে আমাদের ডট পণ্যটিকে সর্বাধিক করতে হবে। একটি জিনিস আমাদের মনে রাখতে হবে যে আমরা প্রদত্ত অ্যারেগুলিতে উপাদানগুলির ক্রম পরিবর্তন করব না। ধরুন অ্যারেগুলি হল A =[2, 3, 1, 7, 8], এবং আরেকটি অ্যারে B =[3, 6, 7]। আউটপুট হবে 107। দ্বিতীয় অ্যারের প্রথম এবং তৃতীয় অবস্থানে 0s সন্নিবেশ করার পর আমরা ডট পণ্যটিকে সর্বাধিক করতে পারি। সুতরাং পণ্যটি হবে 2 * 0 + 3 * 3 + 1 * 0 + 7 * 6 + 8 * 7 =107।
এটি সমাধান করার জন্য, আমরা ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব। সুতরাং A এর আকার m, এবং B এর আকার n। আমরা অর্ডারের (n + 1) x(m + 1) ডায়নামিক প্রোগ্রামিংয়ের জন্য একটি টেবিল তৈরি করব এবং এটি 0s দিয়ে পূরণ করব। এখন বাকি কাজগুলি করতে এই ধাপগুলি ব্যবহার করুন -
-
1 থেকে n:
রেঞ্জের মধ্যে i জন্য-
j এর জন্য :=i থেকে m
-
j এর জন্য :=i থেকে m
-
-
-
টেবিল[i, j] :=সর্বোচ্চ(টেবিল[i - 1, j - 1] + A[j - 1] * B[i - 1], টেবিল[i, j - 1])
উদাহরণ
#include <iostream>
using namespace std;
long long int findMaximumDotProd(int A[], int B[], int m, int n) {
long long int table[n+1][m+1];
for(int i = 0; i<=n; i++){
for(int j = 0; j<=m; j++){
table[i][j] = 0;
}
}
for (int i=1; i<=n; i++)
for (int j=i; j<=m; j++)
table[i][j] = max((table[i-1][j-1] + (A[j-1]*B[i-1])) , table[i][j-1]);
return table[n][m] ;
}
int main() {
int A[] = { 2, 3 , 1, 7, 8 } ;
int B[] = { 3, 6, 7 } ;
int m = sizeof(A)/sizeof(A[0]);
int n = sizeof(B)/sizeof(B[0]);
cout << "Maximum dot product: " << findMaximumDotProd(A, B, m, n);
} আউটপুট
Maximum dot product: 107
