目录

• 92. 递归实现指数型枚举
• 神奇的口袋
• 01背包问题

在做题的时候，有的问题就是问你这个东西选或不选的问题。专业说法叫做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那么时间复杂度为2¹⁰⁰⁰太大了。
不过本文主要是讲的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; }

总结

以上是生活随笔为你收集整理的dfs解决选或不选问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。