There are N questions. The ith 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.
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 ith 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 ith question then you get maximally F[i-1][j] points.
AUTHOR’S AND TESTER’S SOLUTIONS:
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 ithiteration of the for loop (*), the value in G array is exactly as in the ith
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.