动态规划——解决最优问题

骑猪看日落 2022-03-15 10:14 235阅读 0赞

说到动态规划，这里先简单看下另一个算法“贪心算法-greedy algorithm”，是一种在每一步选择中都采用在当前状态下**最优或最好**的选择，从而导致结果是最好或最优的算法。也就是，在当前情况下，我们只管按照“心最贪”的思路进行选择即可。

一般我们会分析：1-将求解问题分成若干个子问题；2-对每一个子问题进行求解，得到子问题的局部最优解；3-把子问题的解，局部最优解合成原来问题一个解即可。

解答思路：while 能朝给定总目标前进一步 do    求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；

经典案例：1，找零钱问题：大家一想都能想明白，找钱都是从大面值开始，然后逐步减小；

--------------------

当然贪心算法的局限性还是比较大的，例如最优解，不全是由最优局部解构成的。举个例子：现在电商平台、外卖平台、P2P平台等，最多的莫过于优惠券。例如我要点外卖：有三张券：1张满10元减1.5、2张满8元减1元。如果我买了16元东西，请问怎么推荐用券？我们大脑都非常聪明一看就是用两张8元券。可是想想如果用上边的贪心算法呢？是不是结果就只用了一张10元券，推荐显然不合理。这就需要用到我们今天说的——**动态规划（Dynamic programming）**。

**动态规划**：是一种通过把原问题分解为相对简单子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。其背后的基本思想非常简单，若要解一个给定的问题，我们需要解其不同的子问题，在根基子问题的解得出原问题。子问题非常类似，对每个子问题进行求解，然后**记忆存储**，以便下次需要同一个子问题解时直接查表。

分析归纳一下其特点：1，具有最优子结构；2，子问题重叠；3，有边界；4，子问题独立。

好，接下来，我们来看看优惠券的使用：

/**
     * @author liujiahan
     * @Title: PackageUtil
     * @Copyright: Copyright (c) 2019
     * @Description:
     * @Created on 2019/3/2
     * @ModifiedBy:
     */
    public class PackageUtil {
    
        /**
         * 券的使用限制额度
         */
        private static int weight[] = {10, 8, 8};
        /**
         * 券的价值
         */
        private static int value[] = {3, 2, 2};
        /**
         * maxValue[i][j]保存每一步计算的值，即前边说的记忆存储
         */
        private static int maxValue[][] = new int[17][3];
    
    
        public static void main(String args[]) {
            // 初始化 -1表示没有存储值
            for (int i = 0; i < 17; i++) {
                for (int j = 0; j < 3; j++) {
                    maxValue[i][j] = -1;
                }
            }
            //花费16元
            int r = maxValue(16, 2);
            System.out.println("最大价值:" + r);
            int total = 16;
            //打印输出选取了那几张券
            for (int j = 2; j > 0; j--) {
                if (maxValue[total][j] > maxValue[total][j - 1]) {
                    System.out.println("选择" + j);
                    total = total - weight[j];
                    if (total == 0) {
                        break;
                    }
                }
            }
            if (total > weight[0]) {
                System.out.println("选择" + 0);
            }
        }
    
        /**
         * 动态规划，递归查询最优值
         * 金额和第几张券
          */
        private static int maxValue(int capacity, int count) {
            int mValue;
            // 不等于-1 表示已经计算过。直接取值
            if (maxValue[capacity][count] != -1) {
                mValue = maxValue[capacity][count];
            } else if (count == 0) {
                // 使用第一张券
                if (capacity > weight[0]) {
                    mValue = value[0];
                } else {
                    mValue = 0;
                }
            } else if (capacity >= weight[count]) {
                //注意这里的递归
                if (maxValue(capacity - weight[count], count - 1) + value[count] > maxValue(capacity, count - 1)) {
                    mValue = maxValue(capacity - weight[count], count - 1) + value[count];
                } else {
                    mValue = maxValue(capacity, count - 1);
                }
    
            } else {
                mValue = maxValue(capacity, count - 1);
            }
            maxValue[capacity][count] = mValue;
            return mValue;
        }
    }
    
    //结果：
    最大价值:4
    选择2
    选择1

好，接下来，我们看以下几个问题：

**      一，解题思路：**

1、构造问题所对应的过程。

2、思考过程的最后一个步骤，看看有哪些选择情况。

3、找到最后一步的子问题，确保符合“子问题重叠”，把子问题中不相同的地方设置为参数。

4、使得子问题符合“最优子结构”。

5、找到边界，考虑边界的各种处理方式。

6、确保满足“子问题独立”，一般而言，如果我们是在多个子问题中选择一个作为实施方案，而不会同时实施多个方案，那么子问题就是独立的。

7、考虑如何做备忘录。

8、分析所需时间是否满足要求。

9、写出转移方程式。

**     二，需要注意点：**

**       **1，做备忘录：计算一次，重复使用。上边利用一个数组进行备份保存。

2，时间分析：只要子问题嵌套不是太多的情况下，时间还是非常快的。通过做备忘录，实现计算一次，重复使用，大大降低了时间复杂度。

3，空间分析：由于做了备忘录，空间相对来说使用了很多。如果备忘录选择不合理也很容易造成空间复杂度的大大提升。例如：P2P行业中的返现券使用条件额度都很大，如果直接用这种动态规划，按1递增进行备忘空间复杂度就大大提升。这时候我们就通过“缩容比例”，根据具体业务，将一些不能出现的情况，不进行记忆存储即可。

好，贪心算法相对来说简单，但是适用范围有限。动态规划，大脑思维理解相对来说比较困难，但是对于计算机，通过递归有边界的思路，能够解决大部分“有独立重复子问题的求最优解”问题。

很多算法，我们学习了，在实际运用中，根据业务进行适当的变形，即可达到适合我们自己业务的代码。