Giả sử chúng ta có hai mảng các số nguyên dương kích thước m và n. Các m> n. Chúng ta phải tối đa hóa sản phẩm dấu chấm bằng cách chèn các số không vào mảng thứ hai. Một điều chúng ta phải ghi nhớ rằng chúng ta sẽ không thay đổi thứ tự của các phần tử trong các mảng đã cho. Giả sử các mảng là A =[2, 3, 1, 7, 8] và một mảng khác B =[3, 6, 7]. Đầu ra sẽ là 107. Chúng ta có thể tối đa hóa tích chấm sau khi chèn các số 0 ở vị trí đầu tiên và thứ ba của mảng thứ hai. Vì vậy, sản phẩm sẽ là 2 * 0 + 3 * 3 + 1 * 0 + 7 * 6 + 8 * 7 =107.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng cách tiếp cận Lập trình động. Vậy kích thước của A là m và kích thước của B là n. Chúng ta sẽ tạo một bảng để lập trình động có thứ tự (n + 1) x (m + 1) và điền vào đó là các số 0. Bây giờ, hãy sử dụng các bước sau để thực hiện phần còn lại -
-
Đối với tôi trong phạm vi từ 1 đến n:
-
Đối với j:=i đến m
-
Đối với j:=i đến m
-
-
-
table [i, j]:=max (table [i - 1, j - 1] + A [j - 1] * B [i - 1], table [i, j - 1])
Ví dụ
#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);
} Đầu ra
Maximum dot product: 107