CODEWITHSUNDEEP
algorithm
John Lui
John Lui

Reputation: 1464

What will be the time complexity for this if I implement 0-1 knapsack like this?

So, here is the problem link, http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/, now they have given two solutions, one using recursion and one using DP. On trying to implement it on my own, I implemented the DP solution using the following approach:

int knapSack(int W, int wt[], int val[], int n, int matrix[][100])
{
   // Base Case
   if (n == 0 || W == 0)
       return 0;
   if (matrix[n][W] != 0)
       return matrix[n][W];

   // If weight of the nth item is more than Knapsack capacity W, then
   // this item cannot be included in the optimal solution
   else if (wt[n-1] > W)
   { 
        matrix[n][W] = knapSack(W, wt, val, n-1,matrix);
        return matrix[n][W];
   }
   // Return the maximum of two cases: (1) nth item included (2) not included
   else
   {
        matrix[n][W] = max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1,matrix),
                    knapSack(W, wt, val, n-1,matrix));
        return matrix[n][W];
   }
}

Though the above approach on running gives a correct answer, but I just want to know is this apporoach equivalent to the approach given in the link itself or mine will take more time as compared to theirs? Thanks!

Upvotes: 0

Views: 56

Answers (1)

IVlad
IVlad

Reputation: 43467

Your approach is fine. What you're doing is called memoization, where you save answers once you get them and then simply return them when they are needed again, without recomputing them.

Your solution does suffer from the overhead of recursion, which might make it slightly slower than the iterative version, but it should not be noticeable.

Basically:

  1. Your approach is much faster than their recursive approach, both asymptotically and in practice.

  2. Your approach might be slightly slower than their iterative implementation, but it's probably not even noticeable for any inputs for which you can afford the memory and the time to run both. Asymptotically, your implementation is the same as their iterative implementation.

Upvotes: 1

Related Questions