搜索算法机侧
2021/11/28 1:12:14
本文主要是介绍搜索算法机侧,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
子集和问题
#include <iostream> #include<bits/stdc++.h> using namespace std; int a[10005]; int n,c,sum=0; int flag=0; int ans[10005]={0}; void display(int m) { for(int i=0;i<m;i++) { if(i!=m-1) printf("%d ",ans[i]); else printf("%d\n",ans[i]); } } void Search(int x,int sum,int len) { if(sum>c||flag) return; if(sum==c) { display(len);///输出ans数组 flag=1; return; } for(int i=x;i<n;i++) { if(sum+a[i]<=c) { ans[len]=a[i]; Search(i+1,sum+a[i],len+1);///2 3 3 3 4,一级一级往回返,返到最后i+1=1,而len=0,从3开始 } } // return; } int main() { ios::sync_with_stdio(false); cin>>n>>c; for(int i=0;i<n;i++) { cin>>a[i]; sum+=a[i]; } if(sum<c) cout<<"No Solution!"<<endl; else { Search(0,0,0); if(!flag) cout<<"No Solution!"<<endl; } return 0; }
运动员最佳分配问题
#include<bits/stdc++.h> using namespace std; int p[101][101]; int q[101][101]; int pre[101] = {0};//男女混合优势值最大 int sum = 0;//最佳匹配值 int vis[101] = {0};//标记 int n; void dfs(int i, int m) { if(i == n + 1)//跳出条件 { sum = max(sum, m); return ; } //(所有递归中最大的优势值)就直接推出当前递归就好 if(m + pre[n] - pre[i - 1] < sum)//如果当前的递归总优势,已经<sum { return ; } for(int j = 1; j <= n; j++) { if(!vis[j]) { vis[j] = 1; dfs(i + 1, m + p[i][j] * q[j][i]);//递归 vis[j] = 0; } } } int main(void) { int i; int j; cin >> n; for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { cin >> p[i][j]; } } for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { cin >> q[i][j]; } } for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) { pre[i] = max(pre[i], p[i][j] * q[j][i]);//把男生当作不变量,只看匹配不同女生,计算出男生确定时,匹配女生优势值最大 } pre[i] += pre[i - 1];//后一个人的优势值,是本人优势值加上前一个人的最大优势值 } dfs(1, 0);//深度优先搜索 printf("%d\n", sum); return 0; }
工作分配问题
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f int n; int vis[12]; int a[12][12]; int ans; void dfs(int h,int sum) { if(sum>ans)///剪枝 return; if(sum<ans&&h==n) { ans=sum;///更新可行性结果 return; } for(int j=0;j<n;j++) { if(!vis[j])///遍历第h行没有被遍历过列号为j的元素 { vis[j]=1; dfs(h+1,sum+a[h][j]); vis[j]=0; } } } int main() { ios::sync_with_stdio(false); cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; ans=inf; dfs(0,0); cout<<ans<<endl; return 0; }
整数变换问题
#include <iostream> using namespace std; int mmax; int n,m; char fn[1000]; int search(int step,int sum) { if(step>mmax) return 0; if(sum*3==m||search(step+1,sum*3)) { fn[step]='f'; return 1; } if(sum/2==m||search(step+1,sum/2)) { fn[step]='g'; return 1; } return 0; } int main() { cin>>n>>m; mmax=1; while(!search(1,n)) mmax++; cout<<mmax<<endl; for(int i=mmax;i>=1;i--) { cout<<fn[i]; }cout<<endl; return 0; }
这篇关于搜索算法机侧的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南