Source available on Github.
Wikipedia has detailed description on the Knapsack problem and pseudo code on solving it. However, while implementing it with Elixir, seems that using simple recursion yields cleaner code. This is not the fastest way to solve the problem, but just easy to understand.
Basically, three return points within the recursion:
- if no items, result is 0 and return
- pop the first item. if item weight is over the max limit, return recursion result of the remaining items
- return the max between (current item value + recursion result with the remaining item) or (just the recursion result with the remaining items only)
However, not only it is inefficient, recursion will cause stack overflow error in Java. See the last (disabled) test case. Use -Xss parameter to increase stack size and run it for fun.
