動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃介紹
??動(dòng)態(tài)規(guī)劃比較適合用來(lái)求解最優(yōu)問(wèn)題胧弛，比如求最大值、最小值等等; 與回溯算法相同的是都會(huì)分多級(jí)進(jìn)行計(jì)算, 不同的是會(huì)對(duì)每一級(jí)進(jìn)行合并統(tǒng)計(jì).
??非常典型的, 對(duì)于0-1背包問(wèn)題在指定重量下求取可以獲得的最大重量: 無(wú)論回溯算法還是動(dòng)態(tài)規(guī)劃都對(duì)每一個(gè)物品是否放入和不放入繼續(xù)判斷, 回溯算法往往繼續(xù)遞歸將此級(jí)獲得的信息傳給下一級(jí), 每個(gè)遞歸中這些信息都可能不同; 動(dòng)態(tài)規(guī)劃則對(duì)信息做一個(gè)記錄統(tǒng)計(jì)比如說(shuō)保存在數(shù)組中, 然后直接在這個(gè)數(shù)組上推算下一級(jí).
動(dòng)態(tài)規(guī)劃0-1背包問(wèn)題解法說(shuō)明
假設(shè): 每個(gè)物品的重量分別是 2,2,4,6,3, 物品個(gè)數(shù)為n=5, 允許重量w=9
- 1 建立一個(gè)
n*w(物品個(gè)數(shù)*重量)的數(shù)組, 那么對(duì)于第一級(jí)來(lái)說(shuō)我們可以得到:data[0][2]=data[0][0]=true兩種情況 - 2 對(duì)于第二級(jí), 我們可以得到:
data[1][0+0]=data[1][0+2]=data[1][2+0]=data[2+2]=true三種情況 - 3 依次進(jìn)行, 我們就可以在一個(gè)數(shù)組中保存所有的可能情況了
- 4 同時(shí)我們需要注意的是:
data[n-1]的數(shù)據(jù)僅僅被data[n]用到此后均不需要, 我們甚至不需要n*w的空間
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
C++解法說(shuō)明
void knapsack2(int *item, int n, int w)
{
bool *state = new bool[w+1];
for(int i = 0; i < w; i++)
{
state[i] = false;
}
state[0] = true;
if(item[0] <= w) state[item[0]] = true;
for(int i = 1; i < n; i++)
{
for(int j = w - item[i]; j >= 0; j--)
{
if(state[j]) state[j+item[i]] = true;
}
}
for(int i = w; i >= 0; i--)
{
if(state[i])
{
printf("weight: %d\n", i);
break;
}
}
}
動(dòng)態(tài)規(guī)劃問(wèn)題的特征
LeetCode-120-三角形的最小路徑和, 舉例說(shuō)明!
- 1 后續(xù)階段的狀態(tài)信息可以通過(guò)前一階段推算出來(lái)
- 2 當(dāng)某一階段的狀態(tài)確定后, 就不必關(guān)系之前的狀態(tài); 也不會(huì)被后續(xù)狀態(tài)影響.
- 3 狀態(tài)合并, 優(yōu)于回溯算法的重要優(yōu)點(diǎn)就是能夠去掉很多重復(fù)的子問(wèn)題(或者不必要判斷的子問(wèn)題)
- 4 狀態(tài)轉(zhuǎn)移方程: 最重要的一點(diǎn)是我們需要找到一個(gè)方程能夠?qū)⑸弦患?jí)狀態(tài)轉(zhuǎn)變?yōu)橄乱患?jí), 可以見(jiàn)舉例中的: 解題思路.
強(qiáng)烈建議, 結(jié)合例子看動(dòng)態(tài)規(guī)劃的理論!
