內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會偶爾插入自己的注釋和理解，盡量會完成作業(yè)

14.3動態(tài)規(guī)劃算法

14.3.1應(yīng)用場景：背包問題

背包問題:有一個(gè)背包，容量為4磅，現(xiàn)有如下物品

要求達(dá)到的目標(biāo)為裝入的背包的總價(jià)值最大，并且重量不超出

要求裝入的物品不能重復(fù)

14.3.2動態(tài)規(guī)劃算法介紹

1)????? 動態(tài)規(guī)劃(Dynamic Programming)算法的核心思想是:將大問題劃分為小問題進(jìn)行解決，從而一步步獲取最優(yōu)解的處理算法

2)????? 動態(tài)規(guī)劃算法與分治算法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。

3)????? 與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。(即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解)

4)????? 動態(tài)規(guī)劃可以通過填表的方式來逐步推進(jìn)，得到最優(yōu)解.

?

14.3.3動態(tài)規(guī)劃算法最佳實(shí)踐-背包問題

背包問題:有一個(gè)背包，容量為4磅，現(xiàn)有如下物品

1)????? 要求達(dá)到的目標(biāo)為裝入的背包的總價(jià)值最大，并且重量不超出

2)????? 要求裝入的物品不能重復(fù)

思路分析和圖解

1.????? 背包問題主要是指一個(gè)給定容量的背包、若干具有一定價(jià)值和重量的物品，如何選擇物品放入背包使物品的價(jià)值最大。其中又分01背包和完全背包(完全背包指的是:每種物品都有無限件可用)

2.????? 這里的問題屬于01背包，即每個(gè)物品最多放一個(gè)。而無限背包可以轉(zhuǎn)化為01背包。

3.????? 算法的主要思想，利用動態(tài)規(guī)劃來解決。每次遍歷到的第i個(gè)物品，根據(jù)w[]和v[i]來確定是否需要將該物品放入背包中。即對于給定的n個(gè)物品,設(shè)v[i]、w[i]分別為第i個(gè)物品的價(jià)值(value)和重量(weight),C為背包的容量。再令v[i][j]表示在前i個(gè)物品中能夠裝入容量為j的背包中的最大價(jià)值。

=======================================

則我們有下面的結(jié)果:

(1) v[i][0]=v[0][i]=0;//表示填入表第一行和第一列是0

(2)當(dāng)w[i]>j時(shí): v[i][j]-v[i-1][j];//當(dāng)準(zhǔn)備加入新增的商品的容量大于當(dāng)前背包的容量時(shí)，就直接使用上一個(gè)單元格的裝入策略

(3)當(dāng)j>=w[i]時(shí):v[i][j]=max{v[i-1][j], v[i]+v[i-1][-w[i]]}

//當(dāng)準(zhǔn)備加入的新增的商品的容量小于等于當(dāng)前背包的容量

//裝入的方式:

v[i-1][j]:就是上一個(gè)單元格的裝入的最大值

v[i]:表示當(dāng)前商品的價(jià)值

v[i-1][j-w[i]:裝入i-1商品，到剩余空間j-w[i]的最大值

當(dāng)j>=w[i]時(shí):v[i][j]=max{v[i-1][j],v[i]+v[i-1][j-w[i]]}:

=======================================

4.????? 圖解分析

14.3.4動態(tài)規(guī)劃-背包問題的代碼實(shí)現(xiàn)

14.4KMP算法

14.4.1應(yīng)用場景-字符串匹配問題

字符串匹配問題

1)????? 有一個(gè)字符串 str1="硅硅谷尚硅谷你尚硅尚硅谷你尚硅谷你尚硅你好",和一個(gè)子串 str2="尚硅谷你尚硅你"

2)????? 現(xiàn)在要判斷 str1是否含有str2,如果存在，就返回第一次出現(xiàn)的位置，如果沒有，則返回-1

14.4.2暴力匹配算法

如果用暴力匹配的思路，并假設(shè)現(xiàn)在str1匹配到i位置，子串str2匹配到j(luò)位置，則有:

1.????? 如果當(dāng)前字符匹配成功(即str1[i]==str2[j])，則i++，j++，繼續(xù)匹配下一個(gè)字符

2.????? 如果失配（即str1[i]! = str2[j])，令 i=i-(j-1)，j=0。相當(dāng)于每次匹配失敗時(shí)，i回溯，j被置為0。

3.????? 用暴力方法解決的話就會有大量的回溯，每次只移動一位，若是不匹配，移動到下一位接著判斷，浪費(fèi)了大量的時(shí)間。(不可行!)

4.????? 暴力匹配算法實(shí)現(xiàn).

5.????? 代碼：

14.4.3KMP算法介紹

KMP是一個(gè)解決模式串在文本串是否出現(xiàn)過，如果出現(xiàn)過，最早出現(xiàn)的位置的經(jīng)典算法

Knuth-Morris-Pratt 字符串查找算法，簡稱為“KMP算法”，常用于在一個(gè)文本串S內(nèi)查找一個(gè)模式串Р的出現(xiàn)位置，這個(gè)算法由Donald Knuth、Vaughan Pratt、James H.Morris三人于1977年聯(lián)合發(fā)表，故取這3人的姓氏命名此算法.

KMP方法算法就利用之前判斷過信息，通過一個(gè)next數(shù)組，保存模式串中前后最長公共子序列的長度，每次回溯時(shí)，通過next數(shù)組找到，前面匹配過的位置，省去了大量的計(jì)算時(shí)間

參考資料：https://www.cnblogs.com/zzuuoo666/p/9028287.html

?

14.4.4KMP算法最佳應(yīng)用-字符串匹配問題

字符串匹配問題:

1.? ? ? 有一個(gè)字符串 str1= "BBC ABCDAB ABCDABCDABDE"，和一個(gè)子串str2="ABCDABD"

2.????? 現(xiàn)在要判斷str1是否含有str2,如果存在，就返回第一次出現(xiàn)的位置,如果沒有，則返回-1

3.????? 要求:使用KMP算法完成判斷，不能使用簡單的暴力匹配算法.

?? 思路分析圖解

舉例來說，有一個(gè)字符串Str1=“BBC ABCDAB ABCDABCDABDE”，判斷，里面是否包含另一個(gè)字符串Str2 =“ABCDABD”?

1.???? ? 首先，用Str1的第一個(gè)字符和Str2的第一個(gè)字符去比較，不符合，關(guān)鍵詞向后移動一位

2.???? ? 重復(fù)第一步，還是不符合，再后移

3.???? ? 一直重復(fù)，直到Str1有一個(gè)字符與Str2的第一個(gè)字符符合為止

4.???? ? 接著比較字符串和搜索詞的下一個(gè)字符，還是符合。

5.???? ? 遇到Str1有一個(gè)字符與Str2對應(yīng)的字符不符合。

6.???? ? 這時(shí)候，想到的是繼續(xù)遍歷str1的下一個(gè)字符，重復(fù)第1步。(其實(shí)是很不明智的，因?yàn)榇藭r(shí)BCD己經(jīng)比較過了，沒有必要再做重復(fù)的工作，一個(gè)基本事實(shí)是，當(dāng)空格與D不匹配時(shí)，你其實(shí)知道前面六個(gè)字符是”ABCDAB”。KMP算法的想法是，設(shè)法利用這個(gè)已知信息，不要把”搜索位置”移回已經(jīng)比較過的位置，繼續(xù)把它向后移，這樣就提高了效率。)

7.???? ? 怎么做到把剛剛重復(fù)的步驟省略掉﹖可以對str2計(jì)算出一張《部分匹配表》，這張表的產(chǎn)生在后面介紹

8.???? ? 已知空格與D不匹配時(shí)，前面六個(gè)字役”ABCDAB”是匹配的。查表可知，最后一個(gè)匹配字符B對應(yīng)的”部分匹配值”為2，因此按照下面的公式算出向后移動的位數(shù):

移動位數(shù)=己匹配的字符數(shù)-對應(yīng)的部分匹配值

因?yàn)?-2等于4，所以將搜索詞向后移動4位。

9.???? ? 因?yàn)榭崭衽cC不匹配，搜索詞還要繼續(xù)往后移。這時(shí)，已匹配的字符數(shù)為2(”AB")，對應(yīng)的”部分匹配值”為0。所以，移動位數(shù)=2-0，結(jié)果為2，于是將搜索詞向后移2位。

10.? 因?yàn)榭崭衽cA不匹配，繼續(xù)后移一位。

11.? 逐位比較，直到發(fā)現(xiàn)c與D不匹配。于是，移動位數(shù)=6-2，繼續(xù)將搜索詞向后移動4位。

12.? 逐位比較，直到搜索詞的最后一位，發(fā)現(xiàn)完全匹配，于是搜索完成。如果還要繼續(xù)搜索（即找出全部匹配)，移動位數(shù)=7-0，再將搜索詞向后移動7位，這里就不再重復(fù)了。

13.? 介紹《部分匹配表》怎么產(chǎn)生的先介紹前綴，后綴是什么

“部分匹配值”就是”前綴”和”后綴”的最長的共有元素的長度。以”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.? ”部分匹配”的實(shí)質(zhì)是，有時(shí)候，字符串頭部和尾部會有重復(fù)。比如,”ABCDAB”之中有兩個(gè)”AB"，那么它的”部分匹配值”就是2(”AB”的長度)。搜索詞移動的時(shí)候，第一個(gè)”AB”向后移動4位(字符串長度-部分匹配值)，就可以來到第二個(gè)”AB”的位置。

到此KMP算法思想分析完畢!

?? 看老師代碼實(shí)現(xiàn)