01背包
有n種物品，一個承重量為m的背包奕剃，每種物品最多只能拿一個或者不拿，且每個物品都有價值v[i]和重量w[i]纵朋，問怎么拿使背包內(nèi)物品價值最大。
定義dp[i][j]表示走到第i個物品操软，背包重量為j時的價值宪祥。
轉移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
dp[i-1][j]表示不拿當前物品聂薪，背包重量為j時的價值
dp[i-1][j-w[i]] + v[i]表示當前拿過后品山，背包重量為j時的價值
for(int i=1; i<=n; i++){
for(int j=0; j<=m; j++){
if(j >= w[i]){//當前承重量為j時能放進
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
}else
dp[i][j] = dp[i-1][j];
}
}
}
//dp[n][m]就是最大價值
可以發(fā)現(xiàn)處理第i個物品時,只需要知道i-1的狀態(tài)就行了。
滾動數(shù)組優(yōu)化：
for(int i=1; i<=n; i++){
for(int j=m; j>=w[i]; j--){//一定是從m到w[i],反了是完全背包了
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
//dp[m]就是最大價值
注意for(int j=m; j>=w[i]; j--)肘交，一定是從大到小，容量大的狀態(tài)需要通過容量小的狀態(tài)轉移過來涯呻。如果先更新容量小的狀態(tài)，就會重復計算复罐，變成完全背包。
完全背包
只有一個條件跟01背包不一樣胀滚，每種物品有無數(shù)個，隨便拿咽笼。
轉移方程dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]), 0 <= k*w[i] <= m
這里k就是拿的數(shù)量。
還是可以用滾動數(shù)組
for(int i=1; i<=n; i++){
for(int j=w[i]; j<=m; j++){//從w[i]到m,跟01相反
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
//dp[m]就是最大價值
先更新小的會影響大的剑刑，很巧妙的地方就是利用重復計算達到拿多個的目的。
多重背包
只是跟前兩個背包條件不一樣，現(xiàn)在每種物品有num[i]個
轉移方程dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]), 0 <= k <= num[i] 且 k*w[i] <= m
跟完全背包差不多施掏。
使用滾動數(shù)組：
void _01(int w, int v, int m){//01背包,
for(int i=m; i>=w; i--){
dp[i] = max(dp[i], dp[i-w] + v);
}
}
void _all(int w, int v, int m){//完全背包
for(int i=w; i<=m; i++){
dp[i] = max(dp[i], dp[i-w] + v);
}
}
//利用上面兩個函數(shù)，多重背包如下
for(int i=1; i<=n; i++){//遍歷每種物品
if(num[i]*w[i] > m){
//背包裝不下所有當前物品七芭，就可以看做完全背包
_all(w[i], v[i], m);
}else{
//裝的下就進行多次01背包
//如果num[i] = 10
//每次拿 1 2 4 3 個
//這里相當于拿了10輪，這么處理更快
int k=1;
while(k<num[i]){
_01(k*w[i], k*v[i], m);
num[i] -= k;
k <<= 1;
}
_01(num[i]*w[i], num[i]*v[i], m);
}
}
//dp[m]就是結果
總結
三種背包都不算難毁菱，不用滾動數(shù)組更好理解，不需要用滾動數(shù)組的時候直接套轉移方程正常dp就行贮庞。
