[Java] 0/1 knapsack problem with dynamic programming

Some time ago we saw a good heuristic for the 0/1 knapsack problem, but it was a heuristic and as the testing demonstrate, there are cases where the optimal solution is missed.

The only way to determine the actual optimal solution is to consider all possibilities and therefore compute a 2D (or more, depending on the constraints) matrix which we would later scan to identify which items have been chosen to reach the computed optimal solution.
The matrix rows indicate the items and the columns indicate all weights from 0 up to the maximum bag capacity.


Note: it would be possible to derive the optimal value using a single array, but by doing so, we would lose our ability to determine which items are part of the solution itself.

Gotcha: the matrix we use is initialized with zeroes for the 0-pick row (obviously), therefore the size of it and the size of the input are off by 1. This has to be noted to avoid confusion while computing the solution, the i-th element in the matrix is actually the i-th - 1 element in our item list. Same goes for the weight since we compute all best picks from the impossible 0 weight bag to the maximum capacity, although in this case it's simply an initialization issue :)

Now, since we are in the 0/1 problem type, calculating the solution boils down to: do we pick this item or not.
Therefore our reasoning has to be: starting from the lowest bag capacity up to the actual bag size we need to compute the best choice of items for that weight; so for each item we walk from 0 all the way up to the maximum bag capacity and ask ourselves if for the weight being considered it would be a good choice to pick the item or it would be better to keep whatever other items are the best for that same total weight.
Eg: instead of picking a single 5kg item it might be better to pick two items weighing 2kg and 3kg.

An item is the best choice if for the exact weight we're considering its value is better than the best value we found for the that weight or it can be added to the best result for a lower weight while staying within the weight limits.

This runs in O(NxM) time where N is the number of items and M is the maximum bag capacity, and also uses O(NxM) additional space.

After we calculated the matrix, to find which items are part of the result, we can simply walk back from the last cell (which contains the maximum attainable value) using this criteria: if the item in the current cell added value over the previous row (the last pick for the same weight), then it is part of the solution and the next item has to be searched for in the previous pick up to the weight remaining after we added the current item. Otherwise we keep walking the previous picks for the same weight until we find the time where the best value changed.

This is also O(NxM) time.

You can check my implementation of fillKnapsackDP on my Gist alongside some test cases in KnapsackJTests.