两阵元乘积之和最大的算法

Question

在一次竞赛中有一个问题，要求计算只包含数学和生物学科的班级的成绩。所以，不存在。数学专业的学生&不。生物专业的学生。每个学生都有自己的分数。数学系学生和生物学生的成绩分别存储在数组、mathScore[]和bioScore中。整个类的性能计算如下：( mathScore*bioScore +mathScore 1*bioScore 1+.+mathScoren-1*生物bioScoren 1)

mathScore代表初学数学学生的分数。bioScore也是如此。

现在给定一个值'm'，我们必须使全班的总分最大化。我们可以通过增加或减少任何候选人的分数1，最大的'm‘倍来做到这一点。现在的问题是，你只能增加一个组的分数。不管是数学还是生物。

现在要解决这个问题，根据我的看法，这个问题需要两个步骤。首先是决定选择哪一组，即数学还是生物。第二步是从所选的学生中选择学生，使那些特定(被选)学生的分数增加或减少，从而使成绩最大化。

我试着思考第一步，就是这样:考虑到这是全班的分数

Maths Score :  5  7  4 -3
Bio Score   : -2  3  9  2

使用m=1；所以，我们将迭代数学分数数组。同时对生物系学生的相应成绩进行了比较。所以，我们选择了数学数组。因为如果我们只需要增加一次。那么增加数学数组中的4将是有益的。因为它将使整体表现提高9倍，这是最大的。

第二步的做法也是如此。找出另一组中相应分数最高的分数。增加这一特定元素。

这是个有点粗糙的想法。但这并不能满足所有的可能性。因此，任何帮助都将不胜感激。

我不是大学生。这不是家庭作业。

Answer 1

我们有Sum(Abs(o[i])) == m m > 0，a[i]，b[i]，m修好了。

Sum( (a[i] + o[i]) * b[i]) == Sum(a[i] * b[i]) + Sum(o[i] * b[i])

所以要使它最大化，我们只需要最大化

Sum(o[i] * b[i])

我们有

o[i] * b[i] <= Abs(o[i] * b[i])

由于我们可以选择o[i]符号，所以我们可以最大限度地选择

Sum(Abs(o[i] * b[i]))

这就是

Sum(Abs(o[i]) * Abs(b[i]))

和

Max(Sum(Abs(o[i]) * Abs(b[i]))) <= m * Max(Abs(b[i]))

对于j，b[j] == Max(Abs(b[i]))，o[j] == sign(b[j]) * m，o[i] == 0，我们有

Sum(o[i] * b[i]) == m * Max(Abs(b[i]))

因此，您必须找到两个数组的最大值(绝对值)。

所以在你的例子中

Maths Score :  5  7  (4+m) -3
Bio Score   : -2  3  9      2

还有其他例子：

Maths Score :  5  7  (4-m) -3
Bio Score   : -2  3  -9     2