In most of the knapsack variants we've a linear dependency on the knapsack size M but in case where we've many small items leading to a very large knapsack capacity we need an alternate way of solving it. I read about it here that we can solve it by using shortest path algorithm but I wasn't able to grab the whole concept. Can anyone explain it in simpler words and can comment a little on the implementation part. Here you can find a related problem.