当前位置: 首页 > article >正文

蓝桥杯备考: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;
}


http://www.kler.cn/a/585852.html

相关文章:

  • Android应用出海之Klarna登录以及kakao登录
  • 【DeepSeek】一文详解GRPO算法——为什么能减少大模型训练资源?
  • axis=0 和 axis=1的区分设置matplotlib正常显示中文和负号
  • 在 Django 中通过 `/media/xxxx` URL 访问上传资源的安全性与实践
  • 神经网络中常用语言特性(python)(待完善)
  • GD32F4xx系列单片机-串口配合DMA的使用
  • 悬镜夫子ASPM数字供应链安全态势感知平台
  • JAVA中的多态性以及它在实际编程中的作用
  • 前端笔试高频算法题及JavaScript实现
  • iWebOffice2015 中间件如何在Chrome107及之后的高版本中加载
  • wepy微信小程序自定义底部弹出框功能,显示与隐藏效果(淡入淡出,滑入滑出)
  • Linux中grep、sed和awk常见用法总结
  • vscode怎么debug vue项目
  • 68.Harmonyos NEXT 图片预览组件应用实践(一):相册与社交场景
  • C++刷题(一):顺序表 + 单链表
  • OpenHarmony-XTS测试
  • UE5.5 Niagara初始化粒子模块
  • 【技海登峰】Kafka漫谈系列(八)Controller:Zookeeper模式与KRaft模式
  • STAR Decomposition 一种针对极端事件的信号分解方法 论文精读加复现
  • AI大模型测试用例生成平台