算法思路
DP问题解题思路
01背包问题解题思路
朴素做法
#include<iostream>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]); //如果第i种物品的体积小于体积要求
}
cout << f[n][m] << endl;
return 0;
}
DP优化
注意到
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j],f[i - 1][j - v[i]] + w[i]);
每次计算f[i][j]
时都只用到了f[i - 1][j]
,即计算第i层时,只用到了第i-1层
可以使用滚动数组来优化,用上一层的数据来更新下一层,改二维数组为一维
f[j] = f[j];
if(j >= v[i]) f[j] = max(f[j],f[j - v[i]] + w[i]);
注意f[j] = f[j]
是恒等式可以省略,条件if(j >= v[i])
可以放到循环初始化里
for(int i = 1; i <= n; i++)
for(int j = v[i]; j <= m; j++)
f[j] = max(f[j],f[j - v[i]] + w[i]);
此时是否与之前等价呢?
具体分析看这位大佬的例子
总结就是此时的f[] 还是第i层的数据,我们需要的是第i - 1层的数据,这样就不能实现滚动数组
那么我们可以倒过来,从大到小更新,这样当我们循环到f[8]时 f[4]是还没有更新的第i-1层的数据
由此可以优化成
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j],f[j - v[i]] + w[i]);
那么DP优化后的代码就是
#include<iostream>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
//int f[N][N]; 改为一维数组
int f[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
f[j] = max(f[j],f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}