|
【摘要】 dynamic programming被認(rèn)為是一種與遞歸相反的技術(shù)，遞歸是從頂部開(kāi)始分解，通過(guò)解決掉所有分解出的問(wèn)題來(lái)解決整個(gè)問(wèn)題，而動(dòng)態(tài)規(guī)劃是從問(wèn)題底部開(kāi)始，解決了小問(wèn)題后合并為整體的解決方案，從而解決掉整個(gè)問(wèn)題。 一.動(dòng)態(tài)規(guī)劃算法dynamic programming被認(rèn)為是一種與遞歸相反的技術(shù)，遞歸是從頂部開(kāi)始分解，通過(guò)解決掉所有分解出的問(wèn)題來(lái)解決整個(gè)問(wèn)題，而動(dòng)態(tài)規(guī)劃是從問(wèn)題底部開(kāi)始，解決了小問(wèn)題后合并為整體的解決方案，從而解決掉整個(gè)問(wèn)題。
動(dòng)態(tài)規(guī)劃在實(shí)現(xiàn)上基本遵循如下思路，根據(jù)邊界條件得到規(guī)模較小時(shí)的解，小規(guī)模問(wèn)題合并時(shí)依據(jù)遞推關(guān)系式進(jìn)行，也就是說(shuō)較大規(guī)模的問(wèn)題解可以由較小問(wèn)題的解合并計(jì)算得到。最經(jīng)典易懂的就是使用遞歸算法和動(dòng)態(tài)規(guī)劃算法兩種不同的方式來(lái)計(jì)算斐波那契數(shù)列或求階乘的對(duì)比，動(dòng)態(tài)規(guī)劃算法的特性相當(dāng)于對(duì)計(jì)算過(guò)程進(jìn)行了緩存，避免了不必要的重復(fù)計(jì)算。 本篇通過(guò)幾個(gè)典型的相關(guān)實(shí)例來(lái)學(xué)習(xí)和練習(xí)動(dòng)態(tài)規(guī)劃算法。 二.尋找最長(zhǎng)公共子串題目不難理解，例如在單詞“raven”和“havoc”的最長(zhǎng)公共子串就是av。最容易想到的算法就是暴力求解，也稱(chēng)為貪心算法，在下一篇中會(huì)提供貪心算法暴力求解最長(zhǎng)公共子串的示例代碼。 算法描述如下： 字符串1長(zhǎng)為m,字符串2長(zhǎng)為n,先生成一個(gè)m*n的矩陣L并將其中都填充為0，矩陣中的值L[x,y]表示如果存在公共字符串，那么該字符串在字符串1中的位置為從x-L[x,y]到x，在字符串2中的位置為從y-L[x,y]到y(tǒng)，換句話說(shuō)：L[x,y]記錄了如果當(dāng)前位置為公共子串的截止點(diǎn)時(shí)公共子串的長(zhǎng)度。 遞推關(guān)系式如下: 若str1[x] === str2[y], L[x,y] = L[x-1,y-1] 1; 若str1[x] !== str2[y], L[x,y] = 0; 從圖中可以更清晰地看到動(dòng)態(tài)規(guī)劃算法在尋找公共子串時(shí)的過(guò)程： 
該表從左上角開(kāi)始填空，循環(huán)遍歷每個(gè)格子，如果str1中的字符和str2中的某個(gè)字符相同，則需要找到其左上角格子的數(shù)字，然后加1填在自己的格子里，如果不相等則填0，最終記錄表中最大的值即為最長(zhǎng)公共子串的結(jié)束位置，打印出最長(zhǎng)公共子串也就很容易實(shí)現(xiàn)了。 參考代碼： /**
* 動(dòng)態(tài)規(guī)劃求解最長(zhǎng)公共子串
*/function lcs(str1,str2) { let record = []; let max = 0; let pos = 0; let result = ''; //初始化記錄圖
for(let i = 0; i < str1.length; i ){
record[i] = []; for(let j = 0; j < str2.length; j ){
record[i][j] = 0;
}
} //動(dòng)態(tài)規(guī)劃遍歷
for(let i = 0; i < str1.length; i ){ for(let j = 0; j < str2.length; j ){ if (i === 0 || j === 0) {
record[i][j] = 0;
}else{ if (str1[i] === str2[j]) {
record[i][j] = record[i-1][j-1] 1;
} else {
record[i][j] = 0;
}
} //更新最大值指針
if (record[i][j] > max) {
max = record[i][j];
pos = [i];
}
}
} //拼接結(jié)果
if (!max) { return '';
} else { for(let i = pos ; i > pos - max ; i--){
result = str1[i] result;
} return result;
}
}console.log(lcs('havoc','raven'))console.log(lcs('abbcc','dbbcc'))
三.0-1背包問(wèn)題遞歸求解0-1背包問(wèn)題用遞歸或動(dòng)態(tài)規(guī)劃都可以求解，通過(guò)本例和下一節(jié)的例子就可以對(duì)比兩種算法相反的求解過(guò)程。 背包問(wèn)題是算法中一個(gè)經(jīng)典的大類(lèi)，從簡(jiǎn)單到復(fù)雜一本書(shū)都講不完，本例中僅實(shí)現(xiàn)簡(jiǎn)單的0-1背包問(wèn)題，這類(lèi)問(wèn)題是指被放入背包的物品只能選擇放或者不放，不能只放入一部分。
0-1背包問(wèn)題的描述是這樣的，假設(shè)保險(xiǎn)箱中有n個(gè)物品，他們的尺寸存放在size[ ]數(shù)組中，每一個(gè)的價(jià)值存放在values[ ]數(shù)組中，你現(xiàn)在擁有一個(gè)背包，其容量為capacity，問(wèn)應(yīng)該裝哪些東西進(jìn)背包，使得被裝入的物品總價(jià)值最大。
算法描述和遞推關(guān)系式如下: 如果第n個(gè)物品無(wú)法放入背包，則最大價(jià)值等同于將其他物品放入背包時(shí)能得到的最大價(jià)值： maxValue = knapsack(capacity,size,values,n-1) 如果第n個(gè)物品能夠放入背包，則最大價(jià)值等同于下列兩種情況中較大的一個(gè)： 2.1 放入物品n,maxValue = knapsack(capacity - size[n], size, values, n-1) values[n] 2.2 不放物品n,maxValue = knapsack(capacity, size, values, n-1)
代碼實(shí)現(xiàn)如下： /**
* 遞歸求解0-1背包問(wèn)題
* 算法：
* 1.如果單個(gè)物品體積超出背包容量，則肯定不拿
* 2.如果單個(gè)物品體積未超出背包容量，則問(wèn)題變?yōu)樵谙铝袃煞N情況中取較大的值
* 2.1 放入當(dāng)前物品 knapsack(capacity - size[n-1], size, value, n-1) value[n-1])
* 2.2 不放入當(dāng)前物品 knapsack(capacity, size, value, n-1)
*/function max(a,b) { return a>b?a:b;
}/**
*
* @param {[type]} capacity 背包容量
* @param {[type]} size 物品體積數(shù)組
* @param {[type]} value 物品價(jià)值數(shù)組
* @param {[type]} n 物品個(gè)數(shù)
* @return {[type]} 最大價(jià)值
*/function knapsack(capacity, size, value, n) { //如果沒(méi)有物品或者背包容量為0 則無(wú)法增值
if (n == 0 || capacity == 0 ) { return 0;
} if (size[n-1] > capacity) { //算法步驟1 從最后一個(gè)物品開(kāi)始，如果單個(gè)物品超出容量限制則不放入
return knapsack(capacity, size, value, n-1);
} else { //算法步驟2
return max(knapsack(capacity - size[n-1], size, value, n-1) value[n-1],knapsack(capacity, size, value, n-1));
}
}let value = [4,5,10,11,13];let size = [3,4,7,8,9];let capacity = 16;let n = 5;let result = knapsack(capacity, size, value, n);console.log('result:',result);
可以看到代碼基本只是用程序語(yǔ)言實(shí)現(xiàn)了算法描述并進(jìn)行了一些邊界條件的處理，并沒(méi)有進(jìn)行任何實(shí)現(xiàn)方法上的優(yōu)化，從它不斷調(diào)用自身就可以看出這是一個(gè)很明顯的遞歸方法。在遞歸方法下，由于重復(fù)訪問(wèn)計(jì)算的問(wèn)題，很難打印出最終到底選擇了哪些物品，而在下面的動(dòng)態(tài)規(guī)劃算法的解法中就相對(duì)容易實(shí)現(xiàn)。 四.0-1背包問(wèn)題動(dòng)態(tài)規(guī)劃求解動(dòng)態(tài)規(guī)劃算法來(lái)求解0-1背包問(wèn)題，核心遞推關(guān)系上并沒(méi)有什么差異，但正如開(kāi)頭所講，動(dòng)態(tài)規(guī)劃的優(yōu)勢(shì)就是對(duì)計(jì)算過(guò)的結(jié)果進(jìn)行了緩存，所以采用這個(gè)算法進(jìn)行0-1背包問(wèn)題求解得到最終結(jié)果后，可以再自頂向下反向查詢(xún)從緩存的表格中查出這個(gè)解的實(shí)現(xiàn)路徑，從而就可以判斷每個(gè)物品是否被選入當(dāng)前解。 動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)如下： /**
* 動(dòng)態(tài)規(guī)劃求解0-1背包問(wèn)題
*/function max(a,b) { return a>b?a:b;
}/**
*
* @param {[type]} capacity 背包容量
* @param {[type]} size 物品體積數(shù)組
* @param {[type]} value 物品價(jià)值數(shù)組
* @param {[type]} n 物品個(gè)數(shù)
* @return {[type]} 最大價(jià)值
*/function knapsack(capacity, size, value, n) { //K[n][capacity]表示0~n-1這n個(gè)物品入選時(shí)的最優(yōu)值
let K = []; let pick = []; let result = 0; for (let i = 0; i <= n ; i ){
K[i] = []; for(let j = 0; j <= capacity; j ){ if(j === 0 || i === 0){ //i=0為防御性編程，沒(méi)有實(shí)際意義
//j=0表示背包容量為0，無(wú)法放入故結(jié)果為0
K[i][j] = 0;
} else if (size[i-1] > j){ //如果背包容量比第i個(gè)物品的重量還小，則第i個(gè)物品必然無(wú)法放入，相當(dāng)于前i-1個(gè)物品放入j容量背包時(shí)的最值
K[i][j] = K[i-1][j];
} else { //動(dòng)態(tài)規(guī)劃解,當(dāng)?shù)趇個(gè)物品可以放入時(shí)，K[i][j]等同于放入i時(shí)最值和不放i時(shí)的值取最大
K[i][j] = max(K[i-1][j-size[i-1]] value[i-1], K[i-1][j]);
}
}
}
result = K[n][capacity]; //如何求解到底選了哪些物品?
while(n > 0){ if (K[n-1][capacity - size[n-1]] value[n-1] > K[n-1][capacity]) {
capacity -= size[n-1];
n--;
pick[n] = 1;
} else {
n--;
pick[n] = 0;
}
} console.log('答案的選擇情況為:',pick); return result;
}let value = [4,5,10,11,13];let size = [3,4,7,8,9];let capacity = 16;let n = 5;let result = knapsack(capacity, size, value, n);console.log('結(jié)果:',result);
demo.rar 來(lái)源：華為云社區(qū) 作者：大史不說(shuō)話
|
