初识动态规划

我不是女神ヾ 2023-03-12 10:59 16阅读 0赞

动态规划比较适合用来求解最优解，最大值最小值等问题。他可以显著的降低时间复杂度，提高代码的执行效率。是出了名的难学，难点跟递归类似，求解问题的过程不太符合人类常规的思维方式。对于新手来说，想要入门确实不容易。不过等你掌握了之后你会发现并没有想象中的那么难（小编深有体会，万事开头难）。

下面我通过两个非常经典的例子，来看动态规划是如何演化出来的。实际上你能掌握了这两个例子的解决思路，对于其他动态规划问题，都可以套用来解决了。

### **0-1背包问题** ###

对于不同重量的物品，我们要选择一些物品转入背包中，如何满足背包承受的重量最大的情况，下放入总重量的最大值。

**方法1：回溯思想**

缺点：回溯思想的算法的时间复杂度高，是指数级别的。

如何解决？那没有什么规律，可以有效的降低时间复杂度？

先来看下回溯如何实现：

class Program
        {
            private static int MaxValue = 0;
            private static int MaxM = 9;
            private static int[] weight = new int[] { 2, 2, 4, 6, 3};
    
            /// <summary>
            /// 回溯思想解决
            /// </summary>
            /// <param name="index">第几个物品</param>
            /// <param name="tmpM">当前重量</param>
            static void FlashBackKnapsack(int index, int tmpM)
            {
                if (index >= weight.Length || tmpM >= MaxM)
                {
                    if (W < tmpM && tmpM <= MaxM)
                    {
                        W = tmpM;
                    }
                    return;
                }
    
                FlashBackKnapsack(index + 1, tmpM);          // 不放入第index个物品
                int m = weight[index] + tmpM;
                if (m <= MaxM)
                {
                    tmpM = m;
                    FlashBackKnapsack(index + 1, tmpM);      // 不放入第index个物品
                }
            }
    
            static void Main(string[] args)
            {
                FlashBackKnapsack(0, 0);
                Console.WriteLine(W);
                Console.ReadKey();
            }
    
        }

规律是不是不好找？那我们就举个例子、画个图看看。我们假设背包的最大承载重量是 9。我们有 5 个不同的物品，每个物品的重量分别是 2，2，4，6，3。如果我们把这个例子的回溯求解过程，用递归树画出来，就是下面这个样子：

![format_png][]

递归树中的每个节点表示一种状态，我们用（index,tmpM）来表示。其中，index 表示将要决策第几个物品是否装入背包，tmpM表示当前背包中物品的总重量。比如，（2，2）表示我们将要决策第 2 个物品是否装入背包，在决策前，背包中物品的总重量是 2。

那回溯算法的时间复杂度是多少呢？对于没个物品来说都有两种选择，装进背包或者不装进背包，对于n个物品来说就有 2^n 种选择，所以回溯算法的时间复杂度是O(2^n) 指数级别的。空间复杂度是O(n)。

**优化：**

从递归树中我们会发现，很多子问题的求解是重复的，比如图中的f(2,2)和f(3,4)都被重复计算了两次，所以我们可以将这些重复求解的问题保存起来，当再次计算到f(index,tmpM)时直接取出来用就可以了，这样就可以避免冗余计算。

那如何实现呢？（可以自己先思考下，然后看下面的代码）

class Program
        {
            private static int MaxValue = 0;
            private static int MaxM = 9;
            private static int[] weight = new int[] { 2, 2, 4, 6, 3};
            private static bool[,] PushMax = new bool[weight.Length, MaxM];
    
            /// <summary>
            /// 回溯思想解决
            /// </summary>
            /// <param name="index">第几个物品</param>
            /// <param name="tmpM">当前重量</param>
            static void FlashBackKnapsack(int index, int tmpM)
            {
                if (index >= weight.Length || tmpM >= MaxM)
                {
                    if (W < tmpM && tmpM <= MaxM)
                    {
                        W = tmpM;
                    }
                    return;
                }
    
                if (PushMax[index, tmpM]) return;
                PushMax[index, tmpM] = true;
                FlashBackKnapsack(index + 1, tmpM);          // 不放入第index个物品
                int m = weight[index] + tmpM;
                if (m <= MaxM)
                {
                    tmpM = m;
                    FlashBackKnapsack(index + 1, tmpM);      // 不放入第index个物品
                }
            }
    
    
            static void Main(string[] args)
            {
                FlashBackKnapsack(0, 0);
                Console.WriteLine(W);
                Console.ReadKey();
            }
    
        }

优化之后的代码的执行效率其实跟动态规划没有差别。

**方法2：动态规划**

思路：

我们把求解的过程分为n个阶段，每一个阶段决策一个物品是否放入，就会得到多种不同的重量，对应到递归树中就是多种不同的状态节点。

我们可以通过合并每一层相同的状态集合，只记录不同的状态，然后基于上一层的状态集合来推到下一层的状态集合，这样就保证了每一层的状态不超过maxW(背包的承受重量)种状态。

如下代码用states\[wArr.Length,maxW + 1\],来记录每层可以达到的不同状态。

初始状态每一层的状态都为0，当决策第0个物品时有两种可能：

1.  不放入：states\[0,0\] = true;
2.  放入：states\[0,2\] = true; 其他的都为false

决策第1个物品通过上一层第0个物品的决策来推到下一层：

不放入：上一层所拥有的状态就都可以成立。

放入：m = 上一层的成立状态的质量 + 第1个物品的重量，满足 m <= maxW ，的所有状态都成立。

第2到第n层都重复上面过程，大家可以结合下面的图来理解。不懂的可以自己画一遍图来加深理解（本人就是画了一遍才理解的）

这样我们只要重最后一层中最接近的值就是能放入背包的最大重量。

![format_png 1][]

![format_png 2][]

根据上面的讲解，各位可以试着用代码实现一下，我用c\#实现了一下

/// <summary>
            /// 动态规划解决 
            /// </summary>
            /// <param name="wArr">物品质量集合</param>
            /// <param name="maxW">背包的最大承受重量</param>
            /// <returns></returns>
            private static int DanamicKnapsack(int[] wArr, int maxW)
            {
                bool[,] states = new bool[wArr.Length, maxW + 1];         // 状态集合
                // 初始化第0个物品
                states[0, 0] = true;
                if (wArr[0] <= maxW)
                {
                    states[0, wArr[0]] = true;
                }
    
                for (int i = 1; i < wArr.Length; i++)
                {
                    // 不放入物品
                    for (int j = 0; j <= maxW; j++)
                    {
                        if (states[i - 1, j])                  // 上一层的状态为true,那么下一层也肯定能达到
                        {
                            states[i, j] = states[i - 1, j];
                        }
                    }
    
                    // 放入物品
                    for (int j = 0; j <= maxW - wArr[i]; j++)
                    {
                        if (states[i - 1, j])                 // 上一层的达到的质量 + 该物品的质量 的 状态为true
                        {
                            states[i, j + wArr[i]] = true; 
                        }
                    }
                }
    
                // 输出最接近的maxW的质量
                for (int j = maxW; j >= 0; j--)
                {
                    if (states[wArr.Length - 1, j]) return j;
                }
    
                return 0;
            }

算法写完，老规矩看一下算法的时间复杂度跟空间复杂度，从代码中可以看到最高两层for循环，第一层为要决策的物品个数，第二层为背包所承受的最大质量，所以算法的时间复杂度是O(n\*m); 再来看下空间复杂度，我们用了states\[wArr.Length, maxW + 1\],的二维数组来存储每层达到的状态，所以空间复杂度是也是O(n\*m);这么看来动态规划是用了空间换时间的方式来提升执行效率。

虽然动态规划的执行效率比较高，但是确需要额外的空间来存储每一层的状态，那有什么方法进行优化呢？怎么降低空间消耗？

其实我们只要一个 maxW + 1 的一维数组就可以实现动态规划的转移过程，代码如下

private static int DanamicKnapsack2(int[] wArr, int maxW)
            {
                bool[] states = new bool[maxW + 1];
                states[0] = true;
                if (wArr[0] <= maxW)
                {
                    states[wArr[0]] = true;
                }
    
                for (int i = 1; i < wArr.Length; i++)
                {
                    for (int j = maxW - wArr[i]; j >= 0; j--)
                    {
                        if (states[j])
                        {
                            states[j + wArr[i]] = true;
                        }
                    }
                }
    
                for (int i = maxW; i >= 0; i--)
                {
                    if (states[i]) return i;
                }
                return 0;
            }

### **0-1 背包升级** ###

我们向原有的01背包中引入价值，对于不同物品有不同重量，不同的价值，那如何在背包承受最大重量下，获的价值最大。

回溯算法：

class Program
        {
            private static int MaxValue = 0;
            private static int MaxM = 10;
            private static int[] weight = new int[] { 3, 8, 8, 8, 5, 6 };
            private static int[] value = new int[] { 3, 30, 8, 8, 5, 6 };
    
            static void Main(string[] args)
            {
                FlashBackKnapsack2(0, 0);
                Console.WriteLine(MaxValue);
                Console.ReadKey();
            }
    
            // 01背包升级版
            // 我们现在引入物品价值这一变量。
            // 对于一组不同重量、不同价值、不可分割的物品，我们选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？
            static void FlashBackKnapsack2(int index,int tmpM,int tmpValue)
            {
                if (tmpM == MaxM || index == weight.Length)
                {
                    if (tmpValue > MaxValue) MaxValue = tmpValue;
                    return;
                }
                FlashBackKnapsack2(index + 1, tmpM, tmpValue);
                if (weight[index] <= MaxM - tmpM)
                {
                    FlashBackKnapsack2(index + 1,tmpM + weight[index],tmpValue + value[index]);
                }
            }
    }

针对上面的代码，我们还是照例画出递归树。在递归树中，每个节点表示一个状态。现在我们需要 3 个变量（index, tmpM, tmpV）来表示一个状态。其中，index 表示即将要决策第 i 个物品是否装入背包，tmpM 表示当前背包中物品的总重量，tmpM 表示当前背包中物品的总价值。

![format_png 3][]

在递归树中，有几个节点的 index 和 tmpM 是完全相同的，比如 f(2,2,4) 和 f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4) 这种状态对应的物品总价值更大，我们可以舍弃 f(2,2,3) 这种状态，只需要沿着 f(2,2,4) 这条决策路线继续往下决策就可以。

也就是说，对于 (index, tmpM) 相同的不同状态，那我们只需要保留 tmpV 值最大的那个，继续递归处理，其他状态不予考虑。这样的话回溯算法就没办法用备忘录的方法来记录了。

动态规划怎么记录呢？

同样我们需要决n个物品，每决策一个物品，就通过上一层的决策来推导下一层的状态，我们同样要用states\[n,maxW + 1\]来记录每一层的状态，但这里状态不是 true 和 false，而是 当前状态对应的最大价值 tmpV。

/// <summary>
            /// 
            /// </summary>
            /// <param name="wArr">物品质量集合</param>
            /// <param name="vArr">物品价值集合</param>
            /// <param name="maxW">背包的最大承受重量</param>
            /// <returns></returns>
            private static int DanamicKnapsack3(int[] wArr,int[] vArr, int maxW)
            {
                int[,] states = new int[wArr.Length, maxW + 1];
                // 初始化状态
                for (int i = 0; i < wArr.Length; i++)
                {
                    for (int j = 0; j <= maxW; j++)
                    {
                        states[i,j] = -1;
                    }
                }
                // 决策第一个
                states[0,0] = 0;
                if (wArr[0] <= maxW)
                {
                    states[0, wArr[0]] = vArr[0];
                }
    
                for (int i = 1; i < wArr.Length; i++)
                {
                    // 放入第i个物品
                    for (int j = 0; j < maxW; j++)
                    {
                        if (states[i - 1, j] != -1)
                        {
                            states[i, j] = states[i - 1, j];
                        }
                    }
    
                    // 不放入第i个物品
                    for (int j = 0; j <= maxW - wArr[i]; j++)
                    {
                        if (states[i - 1, j] != -1)
                        {
                            int v = states[i-1,j] + vArr[i];
                            if (v > states[i, j + wArr[i]])         // 保留该状态的最大价值
                                states[i, j + wArr[i]] = v;
                        }
                    }
                }
                int maxValue = 0;
                for (int i = maxW; i >= 0; i--)
                {
                    if (states[wArr.Length - 1, i] > maxValue)
                    {
                        maxValue = states[wArr.Length - 1, i];
                    }
                }
                return maxValue;
            }

时间复杂度是 O(n\*w)，空间复杂度也是 O(n\*w)。 n物品个数，w背包最大承受重量。

### 内容小结 ###

学完本文，不知道你对动态规划是否有个初步的认识了，我来总结一下本文的内容，让你更好的学习下本文的知识点。

今天的内容不涉及动态规划的理论，我通过两个例子，给你展示了动态规划是如何解决问题的，并且一点一点详细给你讲解了动态规划解决问题的思路。这两个例子都是非常经典的动态规划问题，只要你真正搞懂这两个问题，基本上动态规划已经入门一半了。所以，你要多花点时间，真正弄懂这两个问题。

从例子中，你应该能发现，大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划算法，在执行效率方面，要高很多。尽管执行效率提高了，但是动态规划的空间复杂度也提高了，所以，很多时候，我们会说，动态规划是一种空间换时间的算法思想。

[format_png]: /images/20230312/6ce03dad08f3478ea21a8deec46da52c.png
[format_png 1]: /images/20230312/cfd14c9602464c2fbc6ea64471e4e17b.png
[format_png 2]: /images/20230312/5070e77ad6fc4c9c965dd234931bb587.png
[format_png 3]: /images/20230312/639c603b44464c07aa5cb7adc2e62ea7.png