KNPSK - Editorial



The strategy am using is to pick the the next maximum cost values having weights of 1 and 2. Then adding it to m[i-1] and m[i-2] respectively. After which i take the maximum of both as m*. This analysis is correct right?


thanks a lot .it really helps .


Your code is not clear enough but what i think you are trying to do is to select items based on the heaviest seen and assume that will be part of optimal solution for knapsack. That is outright greedy selection and not the same type of greedy algorithm specified in the editorial. The type of greedy strategy specified in the tutorial was derived from the dynamic programming strategy for solving knapsack based on problem specification. If you need clarification email me


Your Java code is not well indented but looking at it, its looks like O(M^2)


Thanks @okekeau


I am getting WA (: plz help


sry…got it AC…was using int intead of long…-_-…realised after “long” time…


Can someone tell me why my solution is giving WA or provide the test case where it is giving WA?
Link to my Code

Code Explanation:
dp[i][0] = answer for capacity i
dp[i][1] = index upto which items of weight 1 have been used + 1
dp[i][2] = index upto which items of weight 2 have been used + 1

Rest should be easy enough for anybody to understand.