1. 消去作为“层数”的那一维
如果状态转移时需要用到这一层和上一层的信息,此时往往需要改变枚举顺序
例如:\(01\) 背包
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[N], v[N];
int f[2][N], n, m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
for(int i = 1; i <= n; i ++ )
for(int j = 0; j <= m; j ++ )
{
f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j]);
if(j >= w[i]) f[i & 1][j] = max(f[i & 1][j], f[(i - 1) & 1][j - w[i]] + v[i]);
}
cout << f[n & 1][m] << endl;
}
2. 将作为“层数”的那一维修改为滚动数组
如果状态转移只会用到这一层和上一层的信息,说明任意时刻我们只会用到两层的信息,因此“层数”那一维只需要两层即可
例如:\(01\) 背包
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
int f[1010];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ ) {
int v, w; cin >> v >> w;
for(int j = m; j >= v; j -- ) { // !!!改变枚举顺序
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[m] << endl;
return 0;
}
3. 总结
通过代码可以看出来:
[消去维度方法]空间节省的更多,毕竟它直接把一维消去了;但是对于可能需要修改代码逻辑(例如枚举顺序)。
[滚动数组方法]空间消耗是[消去维度方法]的两倍;但是它实现起来比较简单,只需要在所有用到层数那一维的地方加上 & 1
即可。