【Java数据结构与算法】动态规划算法和KMP算法

动态规划算法基本介绍

应用场景

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

物品	重量	价格
吉他(G)	1	1500
音响(S)	4	3000
电脑(L)	3	2000

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

基本介绍

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

动态规划算法解决背包问题思路分析

问题介绍

• 背包问题主要是指一个给定容量的背包，若干具有一定价值和重量的物品，如何选择物品放入背包使得物品的价值最大，其中又分01背包和完全背包(完全背包是指：每种物品都有无限件可用)。
• 这里的问题属于01背包，即每个物品最多放一个，而无线背包可以转化为01背包。

思路分析

算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和val[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设val[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量，再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值，可以得出以下结论：

1. v[i][0] = v[0][j] = 0; // 表示填入表第一行和第一列为0
2. 当w[i] > j时，v[i][j] = v[i-1][j]; // 当准备加入新的物品容量大于当前背包的容量时，就直接使用上一个单元格的转入策略
3. 当j >= w[i]时，v[i][j] = Math.max(v[i-1][j],val[i]+v[i-1][j-w[i]]); // 当准备加入的新增的商品容量小于等于当前背包容量，装入的方式为：
   • v[i-1][j]：上一个单元格装入的最大值；
   • val[i]：表示当前商品的价值；
   • v[i-1][j-w[i]：装入i-1个商品，到剩余空间j-w[i]的最大值；

分析图解

动态规划算法解决背包问题代码实现

代码

package com.algorithm.dynamic;

/**
 * @author Joker大雄
 * @data 2022/11/25 - 13:30
 **/
public class KnapsackProblem {
    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];

        // 初始化第一行和第一列(该步骤可以省略)
        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++) {// 不处理第一列
                // 公式
                // 我们推导是从0开始的，但是这里我们从1开始
                // 所以w[i]应该为w[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(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];
                    }
                }
            }
        }
        // 遍历打印v[][]
        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();
        }
        // 输出存入的物品信息，这样输出会有信息冗余
        /*
        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 maxRow = path.length-1; // 先求出path行的最大下标
        int maxCol = path[0].length-1; // 求出path列的最大下标
        System.out.println("----------------------------------");
        while(maxRow> 0 && maxCol > 0){// path从最后开始往前遍历
            if(path[maxRow][maxCol]==1){
                System.out.printf("第%d个物品放入背包\n",maxRow);
                maxCol -= w[maxRow-1]; // 调整背包容量
            }
            maxRow--; // 遍历下一个
        }
    }
}

运行结果

0 0 0 0 0 
0 1500 1500 1500 1500 
0 1500 1500 1500 3000 
0 1500 1500 2000 3500 
----------------------------------
第3个物品放入背包
第1个物品放入背包

Process finished with exit code 0

暴力匹配算法解决字符串匹配问题

应用场景

字符串匹配问题

给定两个字符串 str1=“adc bcd abcdcdabd”,str2=“abc”；

条件：str1 是否包含 str2，若包含就返回第一次出现的位置，不包含就返回-1;

基本介绍

如果用暴力匹配的思路，并假设现在str1匹配到i位置，str2匹配到j位置，则：

1. 如果当前字符匹配成功(即：str1[i]==str2[j])，则i++，j++，继续匹配下一个字符。
2. 如果匹配失败(即：str[i]!=str[j])，令i=i-(j-1)，j=0；相当于每次匹配失败时，i回溯，j被置为0。
3. 用暴力方法解决会存在大量回溯，浪费时间(并不可行)。

代码实现

代码

package com.algorithm.kmp;

/**
 * @author Joker大雄
 * @data 2022/11/26 - 10:43
 **/
public class ViolenceMatch {
    public static void main(String[] args) {
        // 测试暴力匹配
        String str1 = "adc bcd abcdcdabd";
        String str2="abc";
        int index = violenceMatch(str1, str2);
        System.out.println("index="+index);// 包含空格
    }

    // 暴力匹配算法实现
    public static int violenceMatch(String str1, String str2) {
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();
        int s1Len = s1.length;
        int s2Len = s2.length;
        int i = 0, j = 0; // i指向s1，j指向s2
        while (i < s1Len && j < s2Len) {// 保证匹配不越界
            if (s1[i] == s2[j]) {// 匹配成功
                i++;
                j++;
            } else {// 没有匹配成功
                i = i - (j - 1);
                j = 0;
            }
        }
        // 判断匹配是否成功
        if(j == s2Len){
            return i-j;
        }else{
            return -1;
        }
    }
}

运行结果

index=8

Process finished with exit code 0

KMP算法解决字符串匹配问题思路分析

基本介绍

1. KMP是一个解决模式串在文本串是否出现过，如果出现过，得出最早出现的位置的经典算法。
2. Knuth-Morris-Pratt字符串查找算法，简称"KMP算法"，常用于在一个文本串S内查找一个模式串P的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，因此取三人的姓氏命名此算法。
3. KMP算法利用之前判断过的信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，之前匹配过的位置，省去了大量的时间。

最佳应用

字符串匹配问题

1. 有一个字符串str1=“BBC ABCDAB ABCDABCDABDE”，和一个子串str2=“ABCDABD”。
2. 现在要判断str1是否含有str2，如果存在，就返回第一次出现的位置，如果没有返回-1。
3. 要求：使用KMP算法完成判断，不能使用简单的暴力匹配算法。

思路分析

有一个字符串str1=“BBC ABCDAB ABCDABCDABDE”，判断里面是否包含另一个子串str2=“ABCDABD”

1. 首先，用Str1的第一个字符和Str2的第一个字符取比较，不符合，关键词向后移动一位。

   

2. 重复第一步，不符合，继续后移。

   

3. 一直重复，直到Str1有一个字符与Str2的第一个字符相符合为止。

   

4. 接着比较字符串和搜索词的下一个字符。

   

5. 直到遇到Str1有一个字符与Str2对应的字符不符合。

   

6. 这时，想到是继续遍历Str1的下一个字符，重复步骤1。(这么做并不理想，因为BCD此时已经比较过了，没必要重复工作；当空格与D不匹配时，你其实知道前面的字符是"ABCDAB"。KMP算法的思想是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样便能提高效率)

   

7. 怎么做到把刚才重复的步骤省略掉？可以对Str2计算出一张《部分匹配表》。(表的产生之后会介绍)

   

8. 已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。通过查询部分匹配表，知道最后一个字符B对应的"部分匹配值"为2。因此按照下面的公式算出向后移动的位数：

   移动位数 = 已匹配的字符数 - 对应的部分匹配值

   例如上方：6-2=4，所以搜索词向后移动4位。

9. 因为空格与C不匹配，搜索词还要继续向后移。这时，已匹配的字符数位2(“AB”)，所对应的部分匹配值为0；所以，移动位数=2-0=2，于是将搜索词向后移动2位。

   

10. 因为空格与A不匹配，继续后移一位。

    

11. 逐位比较，直到发现C与D不匹配。于是，移动位数=6-2=4，继续将搜索词向后移动4位。

    

12. 逐位比较，直到搜索词的最后一位，发现完全匹配，搜索完成。如果还要继续搜索(即找出全部匹配)，移动位数=7-0=7，再将搜索词向后移动7位，就不再重复了。

    

13. 介绍《部分匹配表》怎么产生的

    先介绍前缀，后缀是什么。

    

    "部分匹配值"就是"前缀"和"后缀"的最长共有元素的长度。

    以"ABCDABD"为例：

    • "A"的前缀和后缀都为空集，共有元素的长度为0；
    • "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
    • "ABC"的前缀为[A,AB]，后缀为[BC,C]，共有元素的长度为0；
    • "ABCD"的前缀为[A,AB,ABC]，后缀为[BCD,CD,D]，共有元素的长度为0；
    • “ABCDA"的前缀为[A,AB,ABC,ABCD]，后缀为[BCDA,CDA,DA,A]，共有元素为"A”，长度为1；
    • “ABCDAB"的前缀为[A,AB,ABC,ABCD,ABCDA]，后缀为[BCDAB,CDAB,DAB,AB,B]，共有元素为"AB”，长度为2；
    • "ABCDABD"的前缀为[A,AB,ABC,ABCD,ABCDA,ABCDAB]，后缀为[BCDABD,CDABD,DABD,ABD,BD,D]，共有元素的长度为0；

14. “部分匹配"的实质是，有时字符串头部和尾部会有重复。比如"ABCDAB"之中有两个"AB”，那么它的"部分匹配值"就是2("AB"的长度)。搜索词移动的时候，第一个"AB"向后移动4位(字符串长度-部分匹配值)，就可以来到第二个"AB"的位置。

    

步骤分析

1. 先得到字串的部分匹配表。
2. 使用部分匹配表完成KMP匹配。

KMP算法解决字符串匹配问题代码实现

代码

package com.algorithm.kmp;

import java.util.Arrays;

/**
 * @author Joker大雄
 * @data 2022/11/26 - 13:22
 **/
public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";
        int[] next = kmpNext(str2); // 获取部分匹配表
        System.out.println(Arrays.toString(next)); // 部分匹配表打印
        // 测试KMP算法
        int index = kmpSearch(str1, str2, next);
        System.out.println("index="+index);
    }
    // kmp搜索算法
    /**
     *
     * @param str1 要查找的字符串
     * @param str2 匹配的的子串
     * @param next 子串对应的部分匹配值表
     * @return 返回找到的下标，没找到返回-1
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        // 遍历
        for (int i = 0,j = 0; i < str1.length(); i++) {
            // 需要考虑str1.charAt(i) != str2.charAt(j)
            // KMP算法核心点
            while(j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j-1];
            }
            if(str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            if(j == str2.length()) { // 找到
                return i - j + 1;
            }
        }
         return -1;
    }

    // 获取字符串(子串)的部分匹配值表
    public static int[] kmpNext(String dest){
        // 创建next数组，保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; // 如果字符串长度为1，部分匹配值就是0
        for (int i = 1,j = 0; i < dest.length(); i++) {

            // 当dest.charAt(i) != dest.charAt(j)
            // 我们需要从next[j-1]获取新的j
            // KMP算法的一个核心点
            while(j > 0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j-1];
            }
            // 当该条件满足，部分匹配值+1
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

运行结果

[0, 0, 0, 0, 1, 2, 0]
index=15

Process finished with exit code 0