動態(tài)規(guī)劃
動態(tài)規(guī)劃算法是通過拆分問題在刺，定義問題狀態(tài)和狀態(tài)之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決诚欠。
01 背包問題
有 N 件物品和一個容量為 V 的背包紫皇。第 i 件物品的體積是 c[i]，價值是 w[i]盆耽。求解將哪些物品裝入背包可使價值總和最大（每一種物品只能放一次）
分析解答
也不多扯皮蹋砚，直入正題。
先看一個簡單的問題摄杂，斐波那契數(shù)列：
dynFib(n) {
let arr = new Array(n).fill(0);
arr[0] = 1;
arr[1] = 1;
for (let i = 2; i < n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
// 返回最后一個
return arr[n - 1];
}
該問題就是一個簡單的動態(tài)規(guī)劃問題,關鍵點在于找到狀態(tài)關系: f(n) = f(n-1) + f(n-2);
回到背包問題坝咐，可以參考上面斐波那契數(shù)列的遞推關系，
假設現(xiàn)在背包容量為 10析恢，有一個物品數(shù)組:
const product = [
{ weight: 2, value: 3},
{ weight: 2, value: 6 },
{ weight: 6, value: 5 },
{ weight: 5, value: 4 },
{ weight: 4, value: 6 },
];
如果背包容量為 0墨坚，那么什么也放不下
如果背包容量為 1，還是什么也放不下
如果背包容量為 2映挂，有兩個物品都為質(zhì)量都為 2泽篮，該放哪一個呢盗尸？
這時需要做一個決策，先放物品 1帽撑，此時價值為 3泼各；此時比較 上一個決策的價值 - 物品 1 的價值 + 放物品 2 的價值 和物品 1 的價值比，取大的當做該容量下的最優(yōu)解
用狀態(tài)方程描述為： f[i][j]= Math.max(f[i-1][j],f[i-1][j]-c[i]]+w[i]); 其中 i 為第 i 件物品（0 開始）, j 為當前背包容量
如果背包容量為 3亏拉，.......
......
直到背包容量為 10扣蜻，得到此時的最優(yōu)解
初始化一個二維矩陣來記錄背包和價值的關系:
this.result = [];
const row = this.product.length;
const col = this.capacity;
for (let i = 0; i < row; i++) {
this.result[i] = new Array(col + 1).fill(0);
}
我們會發(fā)現(xiàn)，每一個狀態(tài)都依賴于上一個狀態(tài)及塘，第一個物品需要比較沒有物品的狀態(tài)做比較莽使，我們需要對 i=0 時做特殊處理，還有一個更巧妙的方法笙僚，初始化一個 -1 的狀態(tài):
this.result[-1] = new Array(col + 1).fill(0);
如下圖吮旅，我們發(fā)現(xiàn)類似于填表的方式，右下角即為背包最大容量時的價值;
觀察下表可以發(fā)現(xiàn)味咳，該矩陣記錄了每一個容量即狀態(tài)的最優(yōu)解庇勃，比如容量 7 時的最優(yōu)解，我們可以找到 7 那一列最下面即 12;
主函數(shù)部分,利用狀態(tài)方程進行最優(yōu)決策槽驶，
calculate() {
const row = this.product.length;
const col = this.capacity;
let product;
for (let i = 0; i < row; i++) {
for (let j = 0; j < col + 1; j++) {
product = this.product[i];
if (j < product.weight) {
this.result[i][j] = this.result[i - 1][j];
} else {
this.result[i][j] = Math.max(
this.result[i - 1][j],
this.result[i - 1][j - product.weight] + product.value
);
}
}
}
delete this.result[-1];
return this.result[row - 1][col];
}
動態(tài)規(guī)劃解決問題主要是兩個:
- 拆分责嚷、劃分問題到某個顆度時，我們可以很輕易的做出決策
- 確定狀態(tài)方程掂铐，比如上面的: f[i][j]= Math.max(f[i-1][j],f[i-1][j]-c[i]]+w[i])
