Karan2116's blog

Saving Memory In Dynamic Programming
By Karan2116, history, 9 years ago, In English

I am trying to practice some problems in dynamic programming. Now there are memory constraints and i want to manage the memory efficiently for which i want to maintain only those rows on which the final answer depends.

For instance in knapsack,I want to maintain only two rows. I am trying it in the following way but failing.

long long int knapSack(long long W, vector<long long> &wt, vector<long long> &val, int n)
{
   long long int i, w;
   long long int K[2][W+1];
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i%2][w] = 0;
           else if (wt[i-1] <= w)
                 K[i%2][w] = max(val[i-1] + K[(i-1)%2][w-wt[i-1]],  K[(i-1)%2][w]);
           else
                 K[i%2][w] = K[(i-1)%2][w];
       }
   }
   return K[n%2][W];
}

Haven't tried it before and could not find some useful material. It would be great if someone can guide.

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One of the fails may be (i-1)%2 because for i = 0 the result is -1.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use this approach to maintain the last two rows:

vector<int> old(n), cur(n);

// Fill cur with initial values

for (int i = 1; i < m; i++)
{
    old.swap(cur);

    for (int j = 0; j < n; j++)
    {
        cur[j] = f(old[j]);
    }
}

// Now cur contains the last row

It is easy and fast.

→ Reply