算法15 十大算法之-二分查找+分治算法+动态规划

1. 二分查找算法(非递归)

二分查找算法(非递归)介绍

1. 前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式
2. 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找
3. 二分查找法的运行时间为对数时间O(log2n)，即查找到需要的目标位置最多只需要log2n步，假设从[0,99]的 队列(100 个数，即 n=100)中寻到目标数 30，则需要查找步数为log2100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)

代码实现

数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找， 要求使用非递归的方式完成.

public class BinarySearchNoRecur {
    public static void main(String[] args) {
        //测试
        int[] arr = {1,2,8,10,11,67,100};
        int index = binarySearch(arr,1);
        System.out.println("index="+index);
    }

    //二分查找的非递归实现
    /**
     *
     * @param arr 要查找的数组 arr是升序排列
     * @param target 要查找的目标
     * @return 返回对应下标
     */
    public static int binarySearch(int[] arr,int target){
        int left = 0;
        int right = arr.length-1;
        while (left<=right){
            int mid = (left+right)/2;
            if (arr[mid]==target){
                return mid;
            }else if (arr[mid]>target){
                right = mid-1;//需要向左边查找
            }else {
                left = mid+1;
            }
        }
        return -1;
    }

}

2. 分治算法

1. 分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或 相似的子问题，再把子问题分成更小的子问题......直到最后子问题可以简单的直接求解，原问题的解即子问题 的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变 换)......
2. 分治算法可以求解的一些经典问题

• 二分搜索
• 大整数乘法
• 棋盘覆盖
• 合并排序
• 快速排序
• 线性时间选择
• 最接近点对问题
• 循环赛日程表
• 汉诺塔

基本步骤

分治法在每一层递归上都有三个步骤:

1. 分解:将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2. 解决:若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3. 合并:将各个子问题的解合并为原问题的解。

分治(Divide-and-Conquer(P))算法设计模式如下:

最佳实践-汉诺塔

• 汉诺塔的传说
  汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小 顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
  假如每秒钟一次，共需多长时间呢?移完这些金片需要 5845.54 亿年以上，太阳系的预期寿命据说也就是数百 亿年。真的过了 5845.54 亿年，地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。
• 汉诺塔游戏的演示和思路分析:
  1. 如果是有一个盘， A->C 如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘
  2. 先把最上面的盘A->B
  3. 把最下边的盘 A->C
  4. 把B塔的所有盘从B->C
• 
• 代码实现

/**
 * @author DSH
 * @date 2020/9/25
 * @description  分治算法 解决汉诺塔问题
 */
public class Hanoitower {
    public static void main(String[] args) {
        hanoiTower(5,'A','B','C');
    }
    //汉诺塔移动的方法
    //使用分治算法
    public static void hanoiTower(int num,char a,char b,char c){
        //如果只有一个盘
        if (num==1){
            System.out.println("第一个盘从"+a+"->"+c);
        }else {
            //如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘
            //1. 先把最上面的所有盘A->B, 移动过程会使用到C
            hanoiTower(num-1,a,c,b);
            //2. 吧最下边的盘A->C
            System.out.println("第"+num+"个盘从"+a+"->"+c);
            //3. 把B塔的所有盘从B->C,移动过程使用到A
            hanoiTower(num-1,b,a,c);
        }
    }
}

3.动态规划算法

应用场景-背包问题

背包问题:有一个背包，容量为 4 磅 ， 现有如下物品

1. 要求达到的目标为装入的背包的总价值最大，并且重量不超出
2. 要求装入的物品不能重复

介绍

1. 动态规划(DynamicProgramming)算法的核心思想是:将大问题划分为小问题进行解决，从而一步步获取最优解 的处理算法
2. 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这 些子问题的解得到原问题的解。
3. 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子 阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
4. 动态规划可以通过填表的方式来逐步推进，得到最优解.

思路分析

1. 要求达到的目标为装入的背包的总价值最大，并且重量不超出
2. 要求装入的物品不能重复
3. 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价 值最大。其中又分 01 背包和完全背包(完全背包指的是:每种物品都有无限件可用)
4. 这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
5. 算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的 n 个物品，设 v[i]、w[i]分别为第 i 个物品的价值和重量，C 为背包的容量。再令 v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值。则我们有下面的结果:

6. 图解分析

代码实现

/**
 * @author DSH
 * @date 2020/9/27
 * @description 动态规划算法解决背包问题
 */
public class KnapsackProblem {
    public static void main(String[] args) {

        int[] w = {1,4,3};//物品的重量
        int[] val = {1500,3000,2000};//物品的价值, 这里的val[i] 就是v[i]
        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];

        //初始化第一行和第一列
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;//将第一列设置为0
        }
        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;//将第一行设置为0
        }
        
        //根据前面的公式进行冬天规划处理
        for (int  i = 1; i  < v.length; i ++) {
            for (int j = 1; j < v[0].length; j++) {
                //公式
                if (w[i-1]>j){//因为程序中的i是从1开始的  ,因此原来公式中的w[i]修改为w[i-1]
                    v[i][j] = v[i-1][j];
                }else {
                    //因为程序中的i是从1开始的  ,因此原来公式中的val[i]修改为val[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
                        path[i][j] = 1;
                    }else {
                        v[i][j] = v[i-1][j];
                    }
                }
            }
        }
        
        //输出 看下目前的情况
        for (int i = 0; i < v.length; i++) {
            for (int j = 0; j < v[i].length; j++) {
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
        //输出最后放入的是哪些商品
        //遍历path , 这样输出会把所有的放入情况都得到,有数据冗余, 其实我们只需要最后的放入
//        for (int i = 0; i < path.length; i++) {
//            for (int j = 0; j < path[i].length; j++) {
//                if (path[i][j]==1){
//                    System.out.printf("第%d个商品放入了背包\n",i);
//                }
//            }
//        }

        //优化输出
        int i = path.length-1;
        int j = path[0].length-1;
        while (i>0&&j>0){//从path的最后开始找
            if (path[i][j]==1){
                System.out.printf("第%d个商品放入了背包\n",i);
                j -= w[i-1];
            }
            i--;
        }

    }
}