[Java] 0/1 Knapsack problem O(n log n) heuristic

The 0/1 knapsack problem is a fairly common problem in daily life and it's unfortunately one of those problems where you must accept that the optimal solution cannot be computed as quickly as you would like, no matter how hard you think about the problem. As a friend put it, "if the solution looks like black magic, there is probably something wrong with it".

The problem description states: given a recipient with a fixed capacity and a set of items, each with a specific weight and value, the goal is to find the subset that maximises the total value of the chosen items while not exceeding the maximum recipient capacity.
In the 0/1 version, you cannot break an object (not possible to only take a fraction of it) so you can only either take it or not.

Sometimes calculating the optimal solution is too expensive or simply unfeasible (eg online knapsack) so a different, possibly suboptimal approach has to be taken. The one described here uses a greedy algorithm and aims at maximising the total value by selecting items after ordering them by desirability in terms of value per space left after they are picked.

The upside is that it runs in linear, or possibly constant, space, depending on how we track the resulting value; it also runs in O(n log n) time with the most expensive operation being an array sort. The algorithm will also work with weights and values equal to or less than 0.

The downside is that with some inputs, we diverge from the optimal solution selecting less value than it should be possible. You can check the code out on my Gist, including an example of suboptimal result (test heuristicFails).

As for the algorithm description, the steps are:

1. For each item calculate how much space would be left if it was chosen by subtracting its weight from the total available weight. If the result is 0, consider it 1. Then multiply this result by the item value so that we get a desirability score
2. Sort the desirability score descending and break ties by preferring lower weighted items first
3. Start picking the first item in the list and track how much space is left, then move on to the next item and choose it if it fits or skip to the next; continue until no more elements are present or the space left is 0

By the way, in the 0/1 fractional knapsack case (items CAN be broken) it is indeed possible to solve the problem optimally in O(n log n) time by applying this algorithm with a slight modification:

1. For each item calculate its desirability score by dividing the item value by its weight
2. Sort the values by descending order (highest value per weight first)
3. Start picking the first item in the list and track how much space is left, then move on to the next item and continue until no more items are left or the next one does not fit anymore. Break this item so that it fits and return.