dfs解决选或不选问题
解决 DFS 问题
2023-09-11 14:15:52 时间
在做题的时候,有的问题就是问你这个东西选或不选的问题。专业说法叫做01背包。
我个人觉的叫选不选问题更能通速易懂。
92. 递归实现指数型枚举
https://www.acwing.com/problem/content/94/
这就是一个典型的选或不选问题。
对于每一个数我们可以选,也可以不选。
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int n;
const int max=20;
int a[20];//用这个数来记录一下我们对于每个数的状态
// 0代表未处理 1代表选 2代表不选
void dfs(int u)//代表当前选的数是第几个(从下标0开始)
{
if(u==n)
{
for(int i=0;i<n;i++)
{
if(a[i]==1)
{
printf("%d ",i+1);
}
}
printf("\n");
return;
}
a[u]=1;//选这个数
dfs(u+1);
a[u]=0;//恢复现场
a[u]=2;//不选这个数
dfs(u+1);
a[u]=0;//恢复现场
}
int main(void)
{
cin>>n;
dfs(0);
}
神奇的口袋
http://codeup.cn/problem.php?cid=100000583&pid=2
这其实也是一个选或者不选的问题。不过加了一点的限制。
要保证体积和为40。
#include<cstdio>
#include<iostream>
using namespace std;
int V=40;
int n;
int a[1005];
int ans=0;
void dfs(int index,int v)//index 当前的第几个物品的判断选不选(从0开始的) v当前的体积
{
if(index==n)
{
if(v==40)
ans++;
return;
}
dfs(index+1,v);//不选
dfs(index+1,v+a[index]);//选
}
int main(void)
{
while(cin>>n)
{
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
dfs(0,0);
printf("%d\n",ans);
ans=0;
}
return 0;
}
01背包问题
这也是选不选的问题,不过是在各种情况中选择价值最大的。
当然本题用dfs()解决是不可以的。因为n的最大值可以为1000那么时间复杂度为21000太大了。
不过本文主要是讲的dfs()的思想。所以列了出来。对于这种数据量大的情况还是用动态规划解决方便。
#include<cstdio>
#include<cstring>
#include<iostream>
#define max 10005
using namespace std;
int n,V;
int w_arr[max];
int v_arr[max];
int M=-1;//保存最大的
void dfs(int index,int v,int w)//v 代表当前的体积 w代表当前的价值
{
if(index==n)
{
if(v<=V)
{
if(w>M)
{
M=w;
}
}
return;
}
dfs(index+1,v,w);//不选
if(v_arr[index]+v<=V)
dfs(index+1,v_arr[index]+v,w_arr[index]+w);//选
}
int main(void)
{
cin>>n>>V;
for(int i=0;i<n;i++)
{
scanf("%d %d",&v_arr[i],&w_arr[i]);
}
dfs(0,0,0);
printf("%d\n",M);
return 0;
}
相关文章
- 阿里云部署Docker(6)----解决删除<none>镜像问题
- 服务器端解决跨域问题的三种方法
- org.apache.hadoop.dfs.SafeModeException: Cannot create ***. Name node is in safe mode的解决
- 解决程序开发中时间格式不对造成的问题
- centos8平台yum无法安装一些常用软件的解决,如:screen,iftop,nethogs
- 【IOS-COCOS2D游戏开发之十八】解决滚屏背景/拼接地图有黑边(缝隙)/图片缩放后模糊透明/图片不清晰【2013年12月13日补充】/动画播放出现毛边以及禁止游戏中自动锁屏问题!
- 解决网上有重名的问题
- Atitit.php nginx页面空白 并返回500的解决
- 成功解决ValueError: feature_names mismatch: [‘f0‘, ‘f1‘, ‘f2‘, ‘f3‘, ‘f4‘] expected f3, f1, f2, f0, f4
- 成功解决PackagesNotFoundError: The following packages are not available from current channels: tensorflo
- 多种方法解决Error querying database. Cause: java.sql.SQLException: No value specified for parameter 1
- Electron在mac下快捷键失效的问题及解决
- VC++解决Windows快捷方式图标不刷新问题(附源码)
- 解决mongodb查询慢的问题
- 解决No registered ‘MultiDeviceIteratorGetNextFromShard‘ OpKernel for GPU devices compatible with node
- docker拉取镜像报错unexpected EOF的解决方法