PROBLEM LINKS:
Author: Vitaliy Herasymiv
Tester: Tasnim Imran Sunny
Editorialist: Tuan Anh
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
There are N questions. The i^{th} question needs T[i] minutes to learn and will give you C[i] × P[i] points in the tests. You have W minutes to learn the questions. Your job is to find which questions to learn to maximise your score.
EXPLANATION:
We need to choose a sub-set of N questions so that the total learning time does not exceed W and the total socore is
as large as possible. With the constraint N ≤ 100 we cannot try out all possible sub-sets since the number of
sub-sets can be 2 ^{100} which is extremely large.
We need to use dynamic programming in this problem. Let F[i][j] be the maximal score you can get if you spend no more than j
minutes to learn some questions amongst the first i questions. Now, there are two cases:
- If you choose to learn the i^{th} question then you get maximally F[i - 1][j - T[i]] + C[i] × P[i] points. Be careful with the case where j < T[i].
- If you do not learn the i^{th} question then you get maximally F[i-1][j] points.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
In the solution of problem setter and the tester an optimization is used to reduce the memory complexity.
With a little modification of the algorithm above we can solve this problem using a one-dimensional array of W elements.
The pseudo code is given below:
FOR i -> 0 to W G[i] = 0 ENDFOR (*)FOR i -> 1 to N FOR j -> W downto 0 G[j] = max(G[j + T[i]], G[j] + C[i] × P[i]) ENDFOR
After the i^{th}iteration of the for loop (*), the value in G array is exactly as in the i^{th}
row of the F array in the original algorithm. Notice that in the second For loop we need to consider the value of j in the decreasing order
so that each time we use G[j] to update G[j + T[i]] we know that the value in G[j] is the optimized value of using j minutes and the first (i - 1) questions only.