01背包
有n
种物品,一个承重量为m
的背包,每种物品最多只能拿一个或者不拿,且每个物品都有价值v[i]
和重量w[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]就是最大价值
可以发现处理第i
个物品时,只需要知道i-1
的状态就行了。
滚动数组优化:
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--)
,一定是从大到小,容量大的状态需要通过容量小的状态转移过来。如果先更新容量小的状态,就会重复计算,变成完全背包。
完全背包
只有一个条件跟01背包不一样,每种物品有无数个,随便拿。
转移方程dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]), 0 <= k*w[i] <= m
这里k
就是拿的数量。
还是可以用滚动数组
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]就是最大价值
先更新小的会影响大的,很巧妙的地方就是利用重复计算达到拿多个的目的。
多重背包
只是跟前两个背包条件不一样,现在每种物品有num[i]
个
转移方程dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]), 0 <= k <= num[i] 且 k*w[i] <= m
跟完全背包差不多。
使用滚动数组:
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);
}
}
//利用上面两个函数,多重背包如下
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]就是结果
总结
三种背包都不算难,不用滚动数组更好理解,不需要用滚动数组的时候直接套转移方程正常dp就行。
网友评论