有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时的价值
1
2
3
4
5
6
7
8
9
10
|
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的状态就行了。
滚动数组优化：
1
2
3
4
5
6
|
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就是拿的数量。
还是可以用滚动数组
1
2
3
4
5
6
|
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
跟完全背包差不多。
使用滚动数组：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
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就行。