如何将递归算法转换为动态规划？

Question

我有这个算法：

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;
}

如何转换为动态规划算法？我尝试了几种想法，但其中 none 似乎可行。所以我卡住了。

P.S。 w 和 v 只是简单的数字数组，没什么特别的。 W只是一个数字。这个算法没有实现任何特定的任务，我只是在一本书中找到它，他们要求为给定的公式实现算法。

更新：

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;
}

这给出了与递归算法不匹配的错误答案。而且好像还在用递归...

我画的递归树

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

Answer 1

我仍然不知道该算法试图做什么，但非递归函数可能是：

   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;
        }

抱歉 'gotos'，我只是发现为这种情况编程更容易。另外我已经重命名了一些你的输入变量不要发疯。

编辑

正如其他人指出的那样，它可以用作背包算法，因此了解它的用途，您可以 optimize/simplify 多一点（这类算法的复杂性随着n)。例如，您可以对输入 Vect_W 值进行排序并用数组替换列表。

 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;
        }

编辑 2

我刚刚发现发布的初始递归算法条件不佳，例如在最佳分支是第一个分支的情况下。我认为它应该有一个额外的条件来避免这种情况：


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

     }

   //[...]

我还在非递归算法中添加了一个条件，它通过检查当新 W 低于最小 vect_W 元素时是否可以正式关闭分支来完成几乎相同的条件。

如何将递归算法转换为动态规划？

How to convert recursive algorithm to dynamic programming?

c#

recursion

dynamic-programming

recursion-schemes