Algorithm to maximize the sum of product of elemen

问题:

There was a question in a contest which requires calculating the performance of the class which contains only Maths and Bio subject. So, there are 'n' no. of maths student & 'n' no. of bio student. Each student has an individual score. Scores of Maths students and Bio Students are stored in arrays mathScore[] and bioScore respectively. The performance of the whole class is calculated as follows: ( mathScore[0]*bioScore[0] + mathScore[1]*bioScore[1] + ....... +mathScore[n-1]*bioScore[n-1] )

With mathScore[0] representing the score of first Maths student. And same is true for bioScore[0].

Now given a value 'm', we have to maximize the overall score of the class. And we can do so by increasing or decreasing the score of any candidate by 1, a maximum of 'm' times. Now the catch is, you can only increase the score of only one group. Either Maths' or Bio's.

Now coming to the solution, according to me, this question requires two step. First is to decide which group to chose, i.e. either Maths or Bio. And the second step is to select the students from that chosen group, so that increasing or decreasing those particular(selected) students' score will maximize the performance.

I've tried thinking about the first step, this way: Consider this is the score of the class

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

With m=1; So, we'll iterate over the Maths score array. And meanwhile comparing the corresponding scores of Bio students. So, we chose the Maths array. Because if we need to increment only one time. Then increasing the 4 in the Maths array would be beneficial. 'Cause it will increase the overall performance by 9. Which is biggest.

And same will be the approach for the second step. Find the score whose corresponding score in the other group is highest. Increase that particular element.

Now, this is a bit rough idea. But its not working for all the possibilities. So, any help would be appreciated.

P.S. I'm not a college student. And this is no homework.

回答1:

We have Sum(Abs(o[i])) == m m > 0, and a[i], b[i], m fixed.

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

So to maximize it, we just have to maximize

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

And we have

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

And as we can choose sign of o[i], we can maximize instead

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

which is

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

and

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

and with j so that b[j] == Max(Abs(b[i])), o[j] == sign(b[j]) * m, o[i] == 0, we have

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

So you have to find maximum of the both array (of absolute value).

So in your example

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

And for other example:

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