मान लीजिए कि हमारे पास 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