CODEWITHSUNDEEP
c#recursiondynamic-programmingrecursion-schemes
vytaute
vytaute

Reputation: 1480

How to convert recursive algorithm to dynamic programming?

I have this algorithm:

static int findMaxRec(int[] w, int[] v, int W, int n)
{
    int max = int.MinValue;
    int res;
    for (int i = 0; i < n; i++)
    {
        if (w[i] <= W)
        {
            if (w[i] == W)
                res = v[i]; // F(0) + v[i] = v[i]
            else
                res = findMaxRec(w, v, W - w[i], n) + v[i];

            max = max < res ? res : max;
        }
    }
    return max;
}

How can I convert it to dynamic programming algorithm? I have tried several ideas but none of them seems to work. So I am stuck.

P.S. w and v are just simple number arrays, nothing fancier. W is just a number. This algorithm does not implement any particular task I just found it in a book where they ask to implement algorithms for given formulas.

UPDATE:

static int findMaxDyn(int[] F, int[] w, int[] v, int W, int n)
{
    int max = int.MinValue;
    int res;
    for (int i = 0; i < n; i++)
    {
        if (w[i] <= W)
        {
            if (F[W - w[i]] == int.MinValue) // calculate only if -inf
            {
                if (w[i] == W)
                    res = v[i]; // F(0) + v[i] = v[i]
                else
                    res = findMaxDyn(F, w, v, W - w[i], n) + v[i];

                max = max < res ? res : max;
                F[W - w[i]] = max;
            }
        }
    }
    return max;
}

This gives wrong answers that do not match to recursive algorithm. And it seems to still use recursion...

Recursion tree that I have drawn when

int [] w = new []{ 4, 3, 2, 1};
int [] v = new []{ 4, 3, 2, 1};    
int W = 4;
int n = 4;

recursion tree

Upvotes: -5

Views: 224

Answers (1)

Amo Robb
Amo Robb

Reputation: 850

I still don't know what the algorithm is trying to do but the non-recursive function could be:

   public static int findMaxRec_NonRecursive(int[] Vect_w, int[] Vect_v, int W, int n)
        {
           
            List<int> prevWValues = new List<int>();
            List<int> prevVValues = new List<int>();
            List<int> prevIndex_i = new List<int>();
            List<int> prevMaxValue = new List<int>();
            int ListIndex = 0, iniIndex = 0, max = int.MinValue;

            startOver:
            
            for (int i = iniIndex; i < n; i++)
            {
                if (Vect_w[i] <= W)
                {                   
                    if (Vect_w[i] == W)                        
                        max = Math.Max(Vect_v[i], max);
                    else
                    {
                        if (prevWValues.Count > ListIndex)
                        {
                            prevWValues[ListIndex] = W;
                            prevIndex_i[ListIndex] = i;
                            prevVValues[ListIndex] = Vect_v[i];
                            prevMaxValue[ListIndex] = max;
                        }
                        else
                        {
                            prevWValues.Add(W);
                            prevIndex_i.Add(i);
                            prevVValues.Add(Vect_v[i]);
                            prevMaxValue.Add(max);
                        }
                        W -= Vect_w[i];
                        ListIndex++;
                        iniIndex = 0;                       
                        max = int.MinValue;
                        goto startOver;
                    }                   
                }
            }

           
            if (ListIndex>0)
            {
                ListIndex--;
                iniIndex = prevIndex_i[ListIndex]+1;
                W = prevWValues[ListIndex];  
                max = Math.Max(max+ prevVValues[ListIndex], prevMaxValue[ListIndex]);
                goto startOver;
            }    
           
            return max;
        }

Sorry for the 'gotos', I just found it easier to program for this case. Also I have renamed a little your input variables not to drive crazy.

EDIT

As others have pointed out, it could be used as a Knapsack algorithm, so knowing what it is intended to do, you could optimize/simplify a little more (the complexity of these kind of algorithms grow exponentially with n). For instance, you can sort the input Vect_W values and replace lists by arrays.

 public static int findMaxRec_NonRecursive(int[] Vect_w, int[] Vect_v, int W, int n)
        {
            Array.Sort(Vect_w, Vect_v);
            n = Math.Min(n, Vect_w.Length);

            //Remove here repeated elements in Vect_w selecting the one with higher Vect_v if uniqueness is not assured

            int minVectW = Vect_w[0];

            int L = W / minVectW + 1;
            int[] prevWValues = new int[L];
            int[] prevVValues = new int[L];
            int[] prevIndex_i = new int[L];
            int[] prevMaxValue = new int[L];
            int ListIndex = 0, iniIndex = n - 1, max = int.MinValue, PrevUsefullIndex = 0;            

            startOver:

            for (int i = iniIndex; i >= 0; i--)
            {                
                if (Vect_w[i] <= W)
                {
                    if (PrevUsefullIndex < i)
                        PrevUsefullIndex = i;

                    if (Vect_w[i] == W)
                        max = Math.Max(Vect_v[i], max);
                    else
                    {
                        int newW = W - Vect_w[i];
                        if (newW < minVectW)
                            max = Math.Max(Vect_v[i], max);
                        else
                        {
                            prevWValues[ListIndex] = W;
                            prevIndex_i[ListIndex] = i;
                            prevVValues[ListIndex] = Vect_v[i];
                            prevMaxValue[ListIndex] = max;

                            W = newW;                       
                            ListIndex++;
                            iniIndex = PrevUsefullIndex;
                            PrevUsefullIndex = 0;
                            max = int.MinValue;
                            goto startOver;
                        }
                    }
                }
            }

            if (ListIndex > 0)
            {
                ListIndex--;
                iniIndex = prevIndex_i[ListIndex] - 1;
                W = prevWValues[ListIndex];
                max = Math.Max(max + prevVValues[ListIndex], prevMaxValue[ListIndex]);
                goto startOver;
            }

            return max;
        }

EDIT 2

I just found out that the initial recursive algorithm posted is not well conditioned, for example in the case where the best branch is the first branch. I think it should have an additional condition to avoid that:


   //[...]
   else
    {          
            int innerMax = findMaxRec(w, v, W - w[i], n);
            if (innerMax == int.MinValue)
                 innerMax = 0;
            res = innerMax + v[i];

     }

   //[...]

I have also added a condition in the non-recursive algorithm that does pretty much the same by checking if the branch can be officialy closed when the new W is lower than the smallest vect_W element.

Upvotes: 1

Related Questions