蓝桥杯备考:01背包之优化问题。
在谈背包的优化的时候,我们先回顾一下之前的数字三角形问题,我们先用这道题进行一下优化,在谈我们01背包的优化
step1:分析状态表示 f[i][j]表示i,j这个格子的最大路径和
step2;分析状态转移方程
填每个格子都需要正上方和左上方的最大路径加该点的权值取最大
so f[i][j] = max(f[i-1][j],f[i-1][j-1]) + a[i][j]
step3 初始化
由于啊我们每个点的权值都是正整数或者0,
所以刚开始的时候我们只要把数组全部初始化为0就行了
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N][N];
int f[N][N];
int main()
{
cin >> n;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=i;j++)
{
cin >> a[i][j];
}
}
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=i;j++)
{
f[i][j] = max(f[i-1][j],f[i-1][j-1])+a[i][j];
}
}
int ret = 0;
for(int i = 1;i<=n;i++)
{
ret = max(ret,f[n][i]);
}
cout << ret << endl;
return 0;
}
接下来我们就来做一下空间优化,如何把二维转换成一维
我们的第一想法一定是开两个数组,第一个数组是填完的数组,第二个数组根据第一个数组从左往右依次填,
其实还能进一步的优化,我们只需要开一个数组,
每个位置应该填成它当前的值+上一个值,但是我们从左往右填的话就会导致填第二个的时候,第一个值已经变成新的了,我们无法保证其正确性,so我们正确的做法就应该是反着填
now 我们修改一下我们的代码
非常简单,我们只需要做两个事情,1.删除dp数组的一维 2.看看需不需要修改遍历顺序,即可
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N][N];
int f[N];
int main()
{
cin >> n;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=i;j++)
{
cin >> a[i][j];
}
}
for(int i = 1;i<=n;i++)
{
for(int j = i;j>=1;j--)
{
f[j] = max(f[j],f[j-1])+a[i][j];
}
}
int ret = 0;
for(int i = 1;i<=n;i++)
{
ret = max(ret,f[i]);
}
cout << ret << endl;
return 0;
}
这就是我们的空间优化,但是对这道题来说,收益其实是不大的,因为我们的空间应该是足够的,but 对背包问题来说,如果我们对背包问题进行了空间优化,它的时间也是同样会被优化的
我们来重新回顾一下我们的01背包问题
先做第一小问:step1:定义状态表示f[i][j]表示从1到i里选出体积不超过j的最大价值
step2:确定状态转移方程
选和不选的结果取最大值
当然了,我们要选某一个格子的话一定要确定这个格子本身体积是不超过v[i][j]的
step3:初始化
直接填表,0是不影响结果的,
step4:结果,结果就存在f[n][m]里
#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=1;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]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
嗯。我们进行一下空间优化,还是老样子,我们先确定一下空间优化的顺序
我们填每一个格子都是需要左边或者它自己的值,如果我们从左往右填的话,更新右边的值的时候左边的已经改完了,so遍历顺序应该还是从右往左,我们修改一下
#include <iostream>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[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;
}
我们再做一下第二小问
step1:定义状态表示 f[i][j]表示从1到i选出恰好等于体积j的最大价值
step2:推导状态转移方程
可以看到和第一小问的推导方程是差不多的
step3初始化,这里我们就要多注意一下了,我们不可能每个格子都能恰好装满,一定是有无效值的,我们可以把所有格子全初始化为负无穷,然后从有效的开始填起,根据无效格子填的格子还是无效的,嗯,除此之外我们要考虑一下边界情况,最上面那层,0,0表示从0个物品选体积为0,这个格子是有效的,应该是0,我们还要考虑一下左边的边界,i从0到m,体积为0,也需要全部填0
好的,我们来实现一下代码
#include <iostream>
#include <cstring>
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=m;j>=v[i];j--)
// {
//
// f[j] = max(f[j],f[j-v[i]]+w[i]);
//
// }
// }
//
// cout << f[m] << endl;
memset(f,-0x3f,sizeof f);
cin >> n >> m;
for(int i =1;i<=n;i++)
{
cin >> v[i] >> w[i];
}
for(int i = 1;i<=n;i++)
{
f[i][0] = 0;
}
for(int i = 1;i<=n;i++)
{
for(int j =1;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]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
老样子,我们继续对这段代码进行空间优化,还是看遍历顺序,去掉一维
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[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;
memset(f,-0x3f,sizeof f);
cin >> n >> m;
for(int i =1;i<=n;i++)
{
cin >> v[i] >> w[i];
}
for(int i = 1;i<=n;i++)
{
f[0] = 0;
}
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]);
}
}
if(f[m]>=0) cout << f[m] << endl;
else cout << 0 << endl;
return 0;
}