c++ - 最大化两个数组元素乘积和的算法

Question

竞赛中有一个问题需要计算仅包含数学和生物科目的类(class)的表现。所以，有'n'不。数学专业的学生 & 'n' 没有。的生物学生。每个学生都有一个单独的分数。数学学生和生物学生的分数分别存储在数组 mathScore[] 和 bioScore 中。全类成绩计算如下:( mathScore[0]*bioScore[0] + mathScore[1]*bioScore[1] + ...... +mathScore[n-1]*bioScore[n-1] )

用 mathScore[0] 表示第一个数学学生的分数。 bioScore[0] 也是如此。

现在给定一个值“m”，我们必须最大化类(class)的总分。我们可以通过将任何候选人的分数增加或减少 1 来实现，最多“m”次。现在要注意的是，你只能增加一组的分数。数学或生物。

现在来解决这个问题，根据我的说法，这个问题需要两个步骤。首先是决定选择哪个组，即数学或生物。第二步是从所选组中选择学生，以便增加或减少这些特定(所选)学生的分数将最大限度地提高表现。

我试过这样思考第一步:考虑这是类(class)的分数

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

m=1;因此，我们将遍历 Maths score 数组。同时比较Bio学生的相应分数。所以，我们选择了 Maths 数组。因为如果我们只需要增加一次。然后增加 Maths 数组中的 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