8个算法思想

将问题的可能解依次列举出来，然后一一带入问题检验，从而从一系列可能解中获得能够解决问题的精确解。需要注意可能解和候选解的筛选条件，可能解之间的影响、代价、穷举的方式。

公鸡一个五块钱，母鸡一个三块钱，小鸡三个一块钱，现在要用一百块钱买一百只鸡，问公鸡、母鸡、小鸡各多少只？

public class Demo1 {
    public static void main(String[] args) {
        for (int i = 0; i <= 20; i++) {
            for (int j = 0; j <= 33; j++) {
                int n = 100 - i - j;
                if (i * 5 + j * 3 + n / 3 == 100 && n%3==0) {
                    System.out.println("公鸡：" + i + "," + "母鸡：" + i + "," + "小鸡：" + (100 - i - j));
                }
            }
        }
    }
}

从已知条件出发，逐步推算出问题的解。计算机在运用递推思想时，大多都是重复性的推理。

每一次推导的结果可以作为下一次推导的的开始，这似乎跟迭代、递归的思想有点类似，不过递推的范畴要更广一些。

问题：有一只兔子，从第3个月开始每月生1只兔子，小兔子长到第3个月开始每个月也会生1只兔子，假如兔子都不死，问每个月的兔子总数是多少？

public class Demo2 {
    //输出10个月，每个月兔子的总数
    public static void main(String[] args) {
        int nums = 0;
        int one_month = 1,two_month = 1;;
        for (int month = 1; month <= 10; month++) {
            if (month < 3) {
                nums = 1;
            } else {
                //本月兔子数等于前面几个月兔子数的和
                nums = one_month+two_month;
                one_month = two_month;
                two_month = nums;
            }
            System.out.println("第" + month + "个月" + nums + "只兔子");
        }
    }

    //递归实现
    public int rabbit(int month){
        if(month<3){
            return 1;
        }else{
            return rabbit(month-1)+rabbit(month-2);
        }
    }
}

[wppay]

在递推中，是逐次对问题进行推导直到获得最终解。而在递归中，则是逐次回归迭代，直到跳出回归。

递归算法实际上是把问题转化成规模更小的同类子问题，先解决子问题，再通过相同的求解过程逐步解决更高层次的问题，最终获得最终的解。

用一句话来形容递归算法的实现，就是在函数或者子过程的内部，直接或间接的调用自己算法。所以在实现的过程中，最重要的是确定递归过程终止的条件，也就是迭代过程跳出的条件判断。否则，程序会在自我调用中无限循环，最终导致内存溢出而崩溃。

递归思想其实就是一个套娃过程。一般官方都是严禁套娃行为的。所以在使用时一定要明确「套娃」举动的停止条件，及时止损。

源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

public class Demo3 {
    public static void main(String[] args) {
        move(3, "石柱1", "石柱2","石柱3");
    }

    public static void move(int n, String from, String buffer, String to) {
        //第一步：递归结束条件
        if (n == 1) {
            System.out.println("from:" + from + " to:" + to);
            return;
        }
        //n-1个圆盘从from->buffer
        move(n - 1, from, to, buffer);
        //将1个圆盘从form -> to
        move(1, from, to, buffer);
        //将n-1个圆盘从buffer->to
        move(n - 1, buffer, from, to);
    }
}

分治，分而治之。

分治算法的核心步骤就是两步，一是分，二是治。

分治算法很像是一种向下管理的思想，从最高级层层划分，将子任务划分给不同的子模块，进而可以进行大问题的拆分，对系统问题的粒度进行细化，寻求最底层的最基本的解。

分治算法主要包括两个维度的处理，一是自顶向下，将主要问题划分逐层级划分为子问题；二是自底向上，将子问题的解逐层递增融入主问题的求解中。

那怎么分？遵循计算机的最擅长的重复运算，划分出来的子问题需要相互独立并且与原问题结构特征相同，这样能够保证解决子问题后，主问题也就能够顺势而解。

怎么治？这就涉及到最基本子问题的求解，我们约定最小的子问题是能够轻易得到解决的，这样的子问题划分才具有意义，所以在治的环节就是需要对最基本子问题的简易求解。

治后如何？子问题的求解是为了主问题而服务的。当最基本的子问题得到解后，需要层层向上递增，逐步获得更高层次问题的解，直到获得原问题的最终解。

通过层层粒度上的划分，将原问题划分为最小的子问题，然后再向上依次得到更高粒度的解。从上而下，再从下而上。先分解，再求解，再合并。

    //归并
    public static void mergeSort(int[] arr) {
        //分配辅助数组
        int[] temp = new int[arr.length];
        msort(arr, temp, 0, arr.length - 1);
    }

    public static void msort(int[] arr, int[] temp, int left, int right) {
        //如果只有一个元素的区域，那么就不需要继续划分
        //只有元素大于等于2的时候可以进行划分
        if (left < right) {
            //找中间点
            int mid = (left + right) / 2;
            //递归划分左半区域
            msort(arr, temp, left, mid);
            //递归划分右半区域
            msort(arr, temp, mid + 1, right);
            //合并
            merge(arr, temp, left, mid, right);
        }
    }

    public static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        //标记左半区第一个未排序的元素
        int l_pos = left;
        //标记右半区第一个未排序的元素
        int r_pos = mid + 1;
        //临时数组元素的下标
        int pos = left;
        //合并
        while (l_pos <= mid && r_pos <= right) {
            if (arr[l_pos] <= arr[r_pos]) {
                //左半区第一个剩余元素更小
                temp[pos++] = arr[l_pos++];
            } else {
                //右半区第一个剩余元素更小
                temp[pos++] = arr[r_pos++];
            }
        }
        //合并左半区剩余的元素
        while (l_pos <= mid) {
            temp[pos++] = arr[l_pos++];
        }
        //合并右半区剩余的元素
        while (r_pos <= right) {
            temp[pos++] = arr[r_pos++];
        }
        //把临时数组中合并后的元素复制回原来的数组
        while (left <= right) {
            arr[left] = temp[left];
            left++;
        }
    }

讲完分治，我们知道分治思想最重要的一点是分解出的子问题是相互独立且结构特征相同的。这一点并不是所有问题都能满足，许多问题的划分的子问题往往都是相互重叠且互相影响的，那么就很难使用分治算法进行有效而又干净的子问题划分。

于是乎，动态规划来了。动态规划同样需要将问题划分为多个子问题，但是子问题之间往往不是互相独立的。当前子问题的解可看作是前多个阶段问题的完整总结。因此这就需要在在子问题求解的过程中进行多阶段的决策，同时当前阶段之前的决策都能够构成一种最优的子结构。这就是所谓的最优化原理。

最优化原理，一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。同时，这样的最优策略是针对有已作出决策的总结，对后来的决策没有直接影响，只能借用目前最优策略的状态数据。这也被称之为无后效性。

动态规划是在目前看来非常不接近人类思维方式一种算法，主要原因是在于人脑在演算的过程中很难对每一次决策的结果进行记忆。动态规划在实际的操作中，往往需要额外的空间对每个阶段的状态数据进行保存，以便下次决策的使用。

动态规划的求解思路如下图解。动归的开始需要将问题按照一定顺序划分为各个阶段，然后确定每个阶段的状态，如图中节点的F₀等。然后重点是根据决策的方法来确定状态转移方程。也就是需要根据当前阶段的状态确定下一阶段的状态。

在这个过程中，下一状态的确定往往需要参考之前的状态。因此需要在每一次状态转移的过程中将当前的状态变量进行记录，方便之后的查找。

动态规划主要就是用来解决多阶段决策的问题，但是实际问题中往往很难有统一的处理方法，必须结合问题的特点来进行算法的设计，这也是这种算法很难真正掌握的原因。

01背包(不能重复)、完全背包(可以重复)。

package WeChat;

/**
 * @author GoodTime0313
 * @version 1.0
 * @Description
 * @date 2021/3/22 21:46
 */
public class Demo6 {
    public static void main(String[] args) {
        //物品的重量
        int[] w = {1, 4, 3};
        //物品的价值
        int[] val = {1500, 3000, 2000};
        //背包的重量
        int m = 4;
        //物品的个数
        int n = val.length;

        //创建二维数组,表
        //v[i][j] 表示在前i个物品中能够装入容量为j的背包种的最大价值
        int[][] v = new int[n + 1][m + 1];
        //为了记录放入商品的情况，定义一个二维数组
        int[][] path = new int[n + 1][m + 1];
        //初始化第一行第一列,这里在本程序中可以不去处理，默认为0
        for (int i = 0; i < v.length; i++) {
            //第一列设置为0 i行0列
            v[i][0] = 0;
        }
        for (int i = 0; i < v[0].length; i++) {
            //设置第一行为0 0行i列
            v[0][i] = 0;
        }

        //根据前面得到的公式动态规划处理
        //不处理第一行第一列
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                //套用公式
                //因为我们的程序i 是从1开始的 所以要减一
                if (w[i - 1] > j) {
                    v[i][j] = v[i - 1][j];
                } else {
                    //因为我们的i是从1开始的，因此公式需要调成从
                    // v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                    //为了记录商品存放的背包的情况，我们不能简单的使用公式,需要使用if else 体现
                    if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
                        v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
                        //把当前的情况记录
                        path[i][j] = 1;
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }

        //输出v
        for (int i = 0; i < v.length; i++) {
            for (int i1 = 0; i1 < v[0].length; i1++) {
                System.out.print(v[i][i1] + " ");
            }
            System.out.println();
        }

        //最终放入了哪些商品
        //有冗余
/*        for (int i = 0; i < path.length; i++) {
            for (int j = 0; j < path[0].length; j++) {
                if (path[i][j]==1){
                    System.out.print("把第"+i+"个商品加入");
                }
            }
            System.out.println();
        }*/
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                System.out.println("把第" + i + "个商品加入");
                //减去重量
                j-=w[i-1];
            }
            i--;
        }
    }
}

贪心算法，我愿称之为最现实的算法思想。

人活在世上，不可能每一个选择都那么恰到好处。那么多的问题，不可能所有问题都能找到最优解。很多问题根本没有准确解，甚至于无解。所以在某些场景下，傻傻的去追求问题的最精确解是没有意义的。

有人说，那还有最优解呢。难道最优解都不要了吗？

没错，许多问题虽然找不到最精确的解，但是的确会存在一个或者一些最优解。但是一定要去追求这些最优解吗？我看不一定。

算法的存在不是单纯的为了对问题求解，更多的是提供一种「策略」。何谓「策略」，解决问题的一种方式，一个角度，一条路。所以，贪心思想是有价值的。

说回贪心算法。从贪心二字就可得知，这个算法的目的就是为了「贪图更多」。但是这种贪心是「目光短浅」的，这就导致贪心算法无法从长远出发，只看重眼前的利益。

具体点说，贪心算法在执行的过程中，每一次都会选择最大的收益，但是总收益却不一定最大。所以这样傻白甜的思路带来的好处就是选择简单，不需要纠结，不需要考虑未来。

贪心算法的实现过程就是从问题的一个初始解出发，每一次都作出「当前最优」的选择，直至遇到局部极值点。贪心所带来的局限性很明显，就是无法保证最后的解是最优的，很容易陷入局部最优的情况。

但是它每一次做选择的速度很快，同时判断条件简单，能够比较快速的给出一种差不多的解决方案。这里的图解我用下图来表示。

这个图表示的是求解对多条直线的交点。很显然，下图中的直线是不存在统一交点的，但是可以通过算法求得统一交点的最优解。若是采用贪心算法，那么在进行迭代时，每一次都会选择离此时位置最近的直线进行更新。这样一来，在经过多次迭代后，交点的位置就会在某一片区域无限轮回跳转。而这片区域也就是能求得出的大致的最优解区域。

旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题，是图问题中最广为人知的问题。

蒹葭苍苍，白露为霜。所谓伊人，在水一方。溯洄从之，道阻且长。溯游从之，宛在水中央。

每每提及回溯，都会忍不住想到「蒹葭」里的这句诗。看到心中所怀念的心上人啊，忍不住逆流而上去追寻她，尽管追随的道路险阻又漫长；又顺流而下继续寻觅，感觉她似乎就在河水中央。回溯算法的过程正如追逐爱情般的艰辛和反复，时而溯洄从之，时而溯游从之。

回溯算法也可称作试探算法，是不是让你回忆起了在女神面前的小心翼翼。简单来说，回溯的过程就是在做出下一步选择之前，先对每一种可能进行试探；只有当可能性存在时才会向前迈进，倘若所有选择都不可能，那么则向后退回原来的位置，重新选择。

这样看起来，回溯算法很像是一种进行中的枚举算法，在行进的过程中对所有可能性进行枚举并判断。常用的应用场景就在对树结构、图结构以及棋盘落子的遍历上。

举一个很简单的例子，看下面图解。假设目的是从最O₀到达O₄，需要对所有节点进行回溯遍历路径。那么回溯算法的过程则需要在前进的每一步对所有可能的路径进行试探。

比方说，O₀节点前进的路径有三条，分别是上中下条的O₁。回溯过程的开始，先走上面的O₁，然后能够到达上面 O₂，但是这时是一条死路。那么就需要从O₂退回到O₁，而此时O₁的唯一选择也走不通，所以还需要从O₁退回到O₀。然后继续试探中间的O₁。

回溯算法的过程就是不断进行这样的试探、判断、退回并重新试探，直至找到一条完整的前进路径。只不过在这个过程中，可以通过「剪枝」等限制条件降低试探搜索的空间，从而避免重复无效的试探。比方说上下的O₂节点，在经过O₀-O₁-O₂的试探之后，就已经验证了该节点不可行性，下次就无须从O₁开始重复对O₂的试探。

回溯思想在许多大规模的问题的求解上都能得到有效的运用。回溯能够将复杂问题进行分步调整，从而在中间的过程中可对所有可能运用枚举思想进行遍历。这样往往能够清地看到问题解决的层次，从而可以帮助更好地理解问题的最终解结构。

在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

public class EightQueens {
    //1.先定义一个max表示共有多少个皇后
    int max = 8;
    //2.定义数组array,保存皇后放置位置的结果，比如
    /*arr = {0,4,7,5,2,6,1,3};
    不使用二维数组表示棋盘，同一维数组表示
    下标+1 表示第几行，从0开始，对应的(值+1)表示第几列*/
    int[] array = new int[max];

    int count = 0;

    public static void main(String[] args) {
        EightQueens queens = new EightQueens();
        //第一个皇后开始在第1行
        queens.check(0);
        //打印多少种可能
        System.out.println(queens.count);
    }

    //5.放置第n个皇后
    //递归check()，每一次都有for循环
    private void check(int n) {
        // n==8 放第九个皇后，说明前面8个已经放好了
        if (n == max) {
            print();
            return;
        }
        //依次放，并判断有没有冲突
        for (int i = 0; i < max; i++) {
            //先把当前皇后n放到该行的第1列
            array[n] = i;
            //判断当放置第n个皇后到i列时是否冲突
            if (judge(n)) {
                //接着方法n+1个皇后，即开始递归回溯
                check(n + 1);
            }
            //如果冲突没有关系，就继续执行，放到本行的下一列
        }
    }

    //4.查看当我们放置第n个皇后，就去检测该皇后是否和前面已经放置的皇后冲突
    /**
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            //1.判断第n个皇后是否和前面第n-1个皇后在同一列上;
            //2.判断第n个皇后是否和第n-1个皇后在同一斜线
            // n从0开始
            //3.是否在同一行(已经解决)
            if (array[i] == array[n] ||
                Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }

    //3.将皇后排列的位置输出
    private void print() {
        count++;
        for (int j : array) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}

模拟思想的理解相比上述思想应该不是什么难事。

许多真实场景下，由于问题规模过大，变量过多等因素，很难将具体的问题抽象出来，也就无法针对抽象问题的特征来进行算法的设计。这个时候，模拟思想或许是最佳的解题策略。

模拟的过程就是对真实场景尽可能的模拟，然后通过计算机强大的计算能力对结果进行预测。这相较于上述的算法是一种更为宏大的思想。在进行现实场景的模拟中，可能系统部件的实现都需要上述几个算法思想的参与。

模拟说起来是一种很玄幻的思想，没有具体的实现思路，也没有具体的优化策略。只能说，具体问题具体分析。

那应该怎么样来图解呢。我的理解是自定义的，任意的输入，不规则的系统响应，但是只为了获得一个可靠的理想的输出。

[/wppay]