01背包
有一個背包，最大負重為W稚照；有n塊寶石蹂空，每件寶石的價值為vi，重量為wi锐锣，i為[1,n]腌闯。求背包能裝下的寶石的最大價值。
典型的動態(tài)規(guī)劃問題雕憔。狀態(tài)表為dp[i][j]姿骏，i為[0,n]，表示寶石的下標斤彼；j為[0,W]分瘦，表示遞增的總負重。其狀態(tài)轉移方程為：
dp[i,j] = dp[i-1][j], j < w[i];
dp[i,j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]), j >= w[i].
note: dp被初始化為全0數(shù)組琉苇。
代碼
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= W; j++)
{
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
由于狀態(tài)轉移方程只用到了相鄰行的狀態(tài)嘲玫，因此可以把狀態(tài)表縮減成一維dp[j]。此時的狀態(tài)轉移方程為：
dp[j] = max(dp[j], dp[j-w[i]] + v[i]), j >= w[i]
note: j從W遞減為1
代碼
for (int i = 1; i <= N; i++)
{
for (int j = W; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
完全背包
有一個背包并扇，最大負重為W去团；有n種寶石，每種寶石的價值為vi穷蛹，重量為wi土陪，i為[1,n]。寶石的數(shù)量無限肴熏。求背包能裝下的寶石的最大價值鬼雀。
狀態(tài)表為dp[j]，狀態(tài)方程也是：
dp[j] = max(dp[j], dp[j-w[i]] + v[i]), j >= w[i]
但是j是從1遞增至W蛙吏，和上面的01背包相反源哩。原因在于每種的寶石的數(shù)量都是無限的鞋吉，是在解決當前問題（i種物品），向有i種物品的背包添加第i種物品励烦；而01背包問題是在解決當前問題（i種物品）谓着，向有i-1種物品的背包添加第i種物品。
代碼
for (int i = 1; i <= N; i++)
{
for (int j = w[i]; j <= W; j++)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
多維背包
有一個背包崩侠，最多能被Wa克a物質和Wb克b物質漆魔；有n種寶石，每種寶石的價值為vi却音，所含ab物質的質量分別為wai克和wbi克改抡。求背包能裝下的寶石的最大價值。
狀態(tài)表為dp[j][k]系瓢，狀態(tài)方程為：
dp[j][k]=max(dp[j][k], dp[[j-wa[i]][[k-wb[i]] + vi)
for (int i = 1; i <= N; i++)
{
for (int j = Wa; j >= wa[i]; j--)
{
for (int k = Wb; k >= wb[i]; k--)
{
dp[j][k] = max(dp[j][k], dp[j - wa[i]][k - wb[i]] + v[i]);
}
}
}
可以擴展至任意維阿纤。
for (int i = 1; i <= N; i++)
{
for (int j = Wj; j >= wj[i]; j--)
{
for (int k = Wk; k >= wk[i]; k--)
{
for (int l = Wl; l >= wl[i]; l--)
{
...
dp[j][k][l]... = max(dp[j][k][l]..., dp[j - wj[i]][k - wk[i]][l - wl[i]]... + v[i]);
}
}
}
}
