크기가 m과 n인 양의 정수로 구성된 두 개의 배열이 있다고 가정합니다. m> n. 두 번째 배열에 0을 삽입하여 내적을 최대화해야 합니다. 한 가지 명심해야 할 것은 주어진 배열에서 요소의 순서를 변경하지 않는다는 것입니다. 배열이 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으로 채울 것입니다. 이제 다음 단계를 사용하여 나머지 작업을 수행하십시오 -
-
범위 1에서 n에 있는 i의 경우:
-
j의 경우 :=i ~ m
-
j의 경우 :=i ~ m
-
-
-
테이블[i, j] :=max(테이블[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