C++で0を挿入して2つの配列の最大内積を求める方法

問題の概要

サイズ m と n の正整数からなる2つの配列があるとします（m > n）。この問題の目的は、2つ目の配列に 0 を挿入することで、2つの配列の内積を最大化することです。ただし、元の配列内の要素の順序を入れ替えることはできません。

例として、配列 A = [2, 3, 1, 7, 8] と配列 B = [3, 6, 7] を考えてみましょう。このときの出力は 107 となります。B の1番目と3番目の位置に 0 を挿入すると、内積は 2 × 0 + 3 × 3 + 1 × 0 + 7 × 6 + 8 × 7 = 107 となり、これが最大値になります。

動的計画法によるアプローチ

この問題は動的計画法（DP）を用いることで効率的に解くことができます。配列 A のサイズを m、配列 B のサイズを n とし、(n + 1) × (m + 1) のサイズのDPテーブルを作成して、すべての要素を 0 で初期化します。その後、以下の手順でテーブルを埋めていきます。

• i を 1 から n まで繰り返す
• 各 i について、j を i から m まで繰り返し、次の遷移式を適用する

table[i, j] = max(table[i - 1, j - 1] + A[j - 1] * B[i - 1], table[i, j - 1])

この遷移式は、「B の i 番目の要素を A の j 番目の要素と掛け合わせてペアにする場合」と「その要素をスキップする場合」のうち、値が大きい方を選ぶことを意味しています。最終的な答えは table[n][m] に格納されます。

C++での実装例

#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