資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在C++中查詢插入0後兩個陣列的最大點積
假設我們有兩個大小分別為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
更新於：2020年1月3日
308 次瀏覽
廣告