14.3动态规划算法 背包问题+14.4暴力匹配+KMP算法
内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili
写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业
14.3动态规划算法
14.3.1应用场景：背包问题
背包问题:有一个背包，容量为4磅，现有如下物品
要求达到的目标为装入的背包的总价值最大，并且重量不超出
要求装入的物品不能重复
14.3.2动态规划算法介绍
1) 动态规划(Dynamic Programming)算法的核心思想是:将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
2) 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
3) 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。(即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解)
4) 动态规划可以通过填表的方式来逐步推进，得到最优解.
14.3.3动态规划算法最佳实践-背包问题
背包问题:有一个背包，容量为4磅，现有如下物品
1) 要求达到的目标为装入的背包的总价值最大，并且重量不超出
2) 要求装入的物品不能重复
思路分析和图解
1. 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和完全背包(完全背包指的是:每种物品都有无限件可用)
2. 这里的问题属于01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
3. 算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品,设v[i]、w[i]分别为第i个物品的价值(value)和重量(weight),C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。
=======================================
则我们有下面的结果:
(1) v[i][0]=v[0][i]=0;//表示填入表第一行和第一列是0
(2)当w[i]>j时: v[i][j]-v[i-1][j];//当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
(3)当j>=w[i]时:v[i][j]=max{v[i-1][j], v[i]+v[i-1][-w[i]]}
//当准备加入的新增的商品的容量小于等于当前背包的容量
//装入的方式:
v[i-1][j]:就是上一个单元格的装入的最大值
v[i]:表示当前商品的价值
v[i-1][j-w[i]:装入i-1商品，到剩余空间j-w[i]的最大值
当j>=w[i]时:v[i][j]=max{v[i-1][j],v[i]+v[i-1][j-w[i]]}:
=======================================
4. 图解分析
14.3.4动态规划-背包问题的代码实现
14.4KMP算法
14.4.1应用场景-字符串匹配问题
字符串匹配问题
1) 有一个字符串 str1="硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好",和一个子串 str2="尚硅谷你尚硅你"
2) 现在要判断 str1是否含有str2,如果存在，就返回第一次出现的位置，如果没有，则返回-1
14.4.2暴力匹配算法
如果用暴力匹配的思路，并假设现在str1匹配到i位置，子串str2匹配到j位置，则有:
1. 如果当前字符匹配成功(即str1[i]==str2[j])，则i++，j++，继续匹配下一个字符
2. 如果失配（即str1[i]! = str2[j])，令 i=i-(j-1)，j=0。相当于每次匹配失败时，i回溯，j被置为0。
3. 用暴力方法解决的话就会有大量的回溯，每次只移动一位，若是不匹配，移动到下一位接着判断，浪费了大量的时间。(不可行!)
4. 暴力匹配算法实现.
5. 代码：
14.4.3KMP算法介绍
KMP是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
Knuth-Morris-Pratt 字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串Р的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H.Morris三人于1977年联合发表，故取这3人的姓氏命名此算法.
KMP方法算法就利用之前判断过信息，通过一个next数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next数组找到，前面匹配过的位置，省去了大量的计算时间
参考资料：https://www.cnblogs.com/zzuuoo666/p/9028287.html
14.4.4KMP算法最佳应用-字符串匹配问题
字符串匹配问题:
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位。
12. 逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配)，移动位数=7-0，再将搜索词向后移动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,DAA]，共有元素为”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”的位置。
到此KMP算法思想分析完毕!
Ø 看老师代码实现
