-5

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

14
  • 3
    What have you tried? What specifically went wrong with this attempt? As a side note you may want to choose better variable names to make things easier. Commented Apr 8, 2021 at 13:39
  • What's the problem this algorithm solves? Commented Apr 8, 2021 at 13:41
  • 1
    While you are right those are prefaced by comment that explain the variable name like // Input: // Values (stored in array v) // Weights (stored in array w) // Number of distinct items (n) // Knapsack capacity (W) Without any comment on naming the variable name must speak for themself. Commented Apr 8, 2021 at 14:08
  • 1
    @Fildor True, but beside the point. Commented Apr 8, 2021 at 14:14
  • 1
    As stated above, what you seem to be trying to solve is known as the "knapsack problem". This might be of interest to you: stackoverflow.com/a/50395293/10608418 Commented Apr 8, 2021 at 14:42

1 Answer 1

1

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.

Sign up to request clarification or add additional context in comments.

2 Comments

Thank you! Now I at least have a clue about what I am doing.
I also think that it actually is a knapsack problem as others mentioned before. I was just given a task where some information was not mentioned so it was difficult to understand.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.