I'm currently doing a algorithm assignment for knapsack problem, the question is as follow:
The size of knapsack is M, and there are N items each with a integer value and integer weight, we need to figure out the optimal maxium weight that we can put into the knapsack.
I'm using dynamic programming to solve this problem and save the result only for current and the previous loops which takes M2 space, although it saves space, the time complexity for it is still O(MN) as there two for loops, is there any way to improve this?
Thanks