CODEWITHSUNDEEP
algorithmrecursiondynamic-programmingknapsack-problem
user10357462
user10357462

Reputation: 53

Knapsack Problem - Recursive solution explanation

I’m having trouble understanding how and why this naive recursive solution works. If I was given this problem for the first time, I’d think of doing an exhaustive search (iteratively) with all possible combinations, recording and returning the maximum value at the end. Can someone please explain this solution?

code from CSDojo

Code from CSDojo

Upvotes: 2

Views: 3133

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

This solution works because the logic is sound. Let's put that logic into words:

Max value for capacity C, using any of the first to nth items:

def KS(n, C):

If we're not using any items or we have no capacity, then we have zero value:

If n == 0 or C == 0:
  result = 0

Otherwise if the weight of this (the nth) item is greater than this capacity (C), use the best result we can get for this capacity (C) without this item. That's the solution for Max value for capacity C, using any of the first to (n-1)th items (remember that the current calculation is looking for KS(n, C) so we're not permitted to use any items after the nth in the list):

else if w[n] > C:
  result = KS(n - 1, C)

Otherwise, let's decide if we should use this item or not:

else:

If we don't use the nth item, that's the same as our previous possibility: the solution for Max value for capacity C, using any of the first to (n-1)th items:

  tmp1 = KS(n - 1, C)

If we do use it, since the current calculation is looking for a solution for capacity C, let's add the current value, v[n], to our solution using any of the previous n-1 items, but with capacity C - current_weight so that together with the current weight, w[n], we will be presenting the solution that still leaves capacity C:

  tmp2 = v[n] + KS(n - 1, C - w[n])

Choose the higher value:

  result = max{ tmp1, tmp2 }

Return the correct result for our current parameters:

return result

Recursion can be a little counter-intuitive. Calling KS(n, C) will generate a whole bunch of calls to "earlier" parameters n - 1, n - 2, etc., and lower capacities, which makes it seem like those calls are happening after the initial call. But actually KS(n, C) is waiting for all those to complete in order to answer its own calculation so we can accurately say it's happening after the "earlier" parameter calls. And many of them might get repeated, when the parameter values coincide, which is why it can be useful to cache them to speed up the routine.

It can also be useful to consider n, C as the "search space" of the formulation. That means we're really restricted to n * C different combinations of parameters. That's why some recursions, like knapsack, are often tabulated as an iteration over n and C (nested for loops, for example).

Upvotes: 3

Henry
Henry

Reputation: 43728

The solution basically tries for the item n to either put it in (only if it still fits in) or to leave it out and then to put in the remaining items as good as possible (recursive calls). This gives the two values tmp1 and tmp2. It then takes the maximum of those.

Upvotes: 0

MBo
MBo

Reputation: 80187

This method might execute exhaustive search.

It is implementation of branch-and-bounds heuristics, where if-condition cuts current branch because it cannot grow further.

Without that cutting algorithm builds full binary tree for all possible subsets (tmp1 and tmp2 are choices - whether we use current item)

Upvotes: 0

Related Questions