EXAM - Editorial ( NCC 2014 )




Authors: Vaibhav Tulsyan, Aditya Sarode

Tester: Vaibhav Tulsyan

Editorialist: Vaibhav Tulsyan




Knapsack Problem


Given the marks for N questions and the corresponding time to solve, find the maximum marks that can be scored in given time T. Marks for any one particular question can be doubled.


Maintain two 2D DP arrays, one being solution to the problem without doubling marks, and another being solution with doubling of marks. For a certain state (i,j), choose max between the value with doubling marks for i’th Question and the value without doubling.


Consider two DP arrays dp1[i][j] and dp2[i][j].
dp1[i][j] represents the solution without doubling the marks of any question.
dp2[i][j] represents the solution with exactly one question’s marks doubled will now.

Now, for dp2[i][j]:

We have two options: Either reject the previously doubled marks, because doubling marks for current ‘i’ is more profitable, or continue with previously doubled value.
That is, we choose the maximum between 2 choices -

  1. Double marks of current i ----> ( dp1 [ i - 1 ] [ j - t [ i ] ] ) + 2 * m [ i ] … ( A )
  2. Dont double marks of current i ----> max( dp2 [ i - 1 ] [ j ], ( dp2 [ i - 1 ][ j - t [ i ] ] + m [ i ] ) … (B)

Hence, dp2 [ i ][ j ] = max ( A , B )

Therefore, the answer is dp2[ N ][ T ] ( 1 - indexed array ).

Complexity: O( N*T )

1 Like

when will the problem visible in peer section? Make it fast please !

1 Like

Shouldn’t the complexity be O(NT) rather than O(N^2)?

Hey, the problems have been put up in the peer section for practice.

Thanks, I’ve made the changes.

Can somebody tell why I am getting WA, https://www.codechef.com/viewsolution/38461555
I have calculated max marks considering original points using knapsack logic then i have considered each element to be doubled then in the remaining time what max marks can be obtained and printed the max marks.
Pls Help.

Pls help