1.完全背包问题原始版本
依次选k(0,1,2,....)个,在没有填满当前状态dp[i][j]的情况下,依次选取dp[i-1][j - k*v[i]] + k * w[i]中的最大值,时间复杂度为O(n^3)
#include<iostream>
using namespace std;
const int N = 1010;
int dp[N][N], n, m;
int v[N], w[N];
int main(){
scanf("%d%d",&n, &m);
for(int i = 1; i <= n; i++){
scanf("%d%d", &v[i], &w[i]);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
for(int k = 0; k * v[i] <= j; k++){
dp[i][j] = max(dp[i][j], dp[i-1][j - k*v[i]] + k * w[i]);
}
}
}
printf("%d\n", dp[n][m]);
return 0;
}
2.完全背包问题优化版
这里发现重复计算了一些状态, 所以可以把第三层循环去掉,时间复杂度优化为O(n^2)
#include<iostream>
using namespace std;
const int N = 1010;
int dp[N][N], n, m;
int v[N], w[N];
int main(){
scanf("%d%d",&n, &m);
for(int i = 1; i <= n; i++){
scanf("%d%d", &v[i], &w[i]);
}
//因为dp[i][j] = max( dp[i-1][j], dp[i-1][j-v[i]] + w[i] , dp[i-1][j - 2*v[i]] + 2*w[i], dp[i-1][j-3*v[i]] + 3*w[i] ....)
//而dp[i][j - v[i]] = max( dp[i-1][j-v[i]], dp[i-1][j - 2*v[i]] + *w[i], dp[i-1][j-3*v[i]] + 2*w[i] ....)
//所以dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dp[i][j] = dp[i - 1][j];
if(j >= v[i]){
dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
}
printf("%d\n", dp[n][m]);
return 0;
}
和0-1背包对比
0-1背包版本
dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
完全背包版本:
dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
可见区别只是 dp[i - 1][j - v[i]]和dp[i][j - v[i]] + w[i]
3.滚动数组再次优化版
这次优化了空间复杂度,使得空间复杂度为O(n)
代码
#include<iostream>
using namespace std;
const int N = 1010;
int dp[N], n, m;
int v[N], w[N];
int main(){
scanf("%d%d",&n, &m);
for(int i = 1; i <= n; i++){
scanf("%d%d", &v[i], &w[i]);
}
for(int i = 1; i <= n; i++){
for(int j = v[i]; j <= m; j++){
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
printf("%d\n", dp[m]);
return 0;
}
和0-1背包滚动数组版本内层循环的枚举顺序对比
0-1背包
for(int j = m; j >= v[i]; j--)
完全背包序for(int j = v[i]; j <= m; j++)