मान लीजिए हमारे पास आकार m और n के दो धनात्मक पूर्णांकों की सरणी हैं। m > n है। हमें दूसरी सरणी में शून्य डालकर डॉट उत्पाद को अधिकतम करना है। एक बात ध्यान रखनी है कि हम दी गई सरणियों में तत्वों के क्रम को नहीं बदलेंगे। मान लीजिए सरणी हैं A = [2, 3, 1, 7, 8], और दूसरी सरणी B = [3, 6, 7]। आउटपुट 107 होगा। हम दूसरी सरणी के पहले और तीसरे स्थान पर 0 डालकर डॉट उत्पाद को अधिकतम कर सकते हैं। तो उत्पाद होगा 2 * 0 + 3 * 3 + 1 * 0 + 7 * 6 + 8 * 7 = 107।
इसे हल करने के लिए, हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे। A का आकार m है, और B का आकार n है। हम (n + 1)x(m + 1) क्रम की डायनामिक प्रोग्रामिंग के लिए एक तालिका बनाएंगे, और इसे 0 से भर देंगे। अब बाकी काम करने के लिए इन चरणों का उपयोग करें:
i को 1 से n तक की रेंज में:
j := i से m तक
j := i से m तक
table[i, j] := max(table[i - 1, j - 1] + A[j - 1] * B[i - 1], table[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
