数据结构
网络
关系数据库管理系统 (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 次浏览
广告