สมมติว่าเรามีจำนวนเต็มบวกสองอาร์เรย์ที่มีขนาด 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:
-
สำหรับ 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
