[Java] Unbounded knapsack algorithm

Taking up again the knapsack challenge I tried some time ago, I decided to solve an easier problem first, the unbounded knapsack.

We already know we need to compute some values in order to find the perfect solution to the problem from past experience :) so this time we'll build our information data structure incrementally, starting from considering the bag with capacity 0 and working up to the input capacity.

The important thing is to convince ourselves that there is NO BETTER SOLUTION than considering all possibilities, with some interesting ways to reduce the number of possibilities though ;)

At each weight increase we want to know what would the best pick(s) be from our items if the maximum weight was the one we're currently evaluating. Therefore the key part is: we need to check ALL items every time to determine whether it's best to pick the item alone OR the item PLUS some of the previous items OR even MORE of the previous items.

If we care only about the maximum value we can achieve, we can easily track this with an integer array or similar, but we would lose the information regarding which and how many items make up our best solution; we can fix this by using some object to track the partial information and update our result in a nice way before returning from the function.

By knowing the best pick at each step, we will reach in O(NxK) time and O(k) space the best solution where N is the number of items and k is the maximum weight the bag can carry.

We can put some improvements in place, for example we can preprocess the items to discard any item that weighs more than what our bag can carry or any item for which a better item exist (more value for same or less weight).

You can check my implementation of fillUnboundedKnapsack on my Gist alongside with some tests in KnapsackJTests and the supporting structures I use.