I was trying this question from spoj http://www.spoj.com/problems/HKNAP/

I am not able to figure out how to deal with such large values of weight which can be 2000000. So I am not able to make the dp array to solve the knapsack problem.

I am not able to figure out how to deal with such large values of weight which can be 2000000. So I am not able to make the dp array to solve the knapsack problem.