1.子集和问题
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
const int N=1e4+5;
int n,m,a[N];
bool vis[N];
int lsum,rsum; //当前已经加到结果中的整数和 余下的数的和
void dfs(int k){ //这里的k是要对第k个数取或者不去的状态进行搜索
if(k>n) return ;
if(lsum==m){
for(int i=1;i<=n;i++){
if(vis[i]) cout<<a[i]<<" ";
}
exit(0); // 找到解后直接退出程序
//exit(0);：立即终止整个程序 不仅仅结束当前函数
//return 0;：正常结束当前函数 在递归中为让这条搜索路径结束
}
if(lsum+a[k]<=m){
//对搜索树的左子树进行搜索剪枝的策略 即不能已经超过目标值了
vis[k]=true; //左子树为不选择该节点
lsum+=a[k],rsum-=a[k];
dfs(k+1);
lsum-=a[k],rsum+=a[k];
}
if(lsum+rsum-a[k]>=m){
//对搜索数的右子树进行搜索剪枝 即若某节点之前不选择的节点过多
//现在即使把剩下没搜索过的数都算上 也已经不够了 就剪枝
// 只对满足的节点的右节点继续搜索
vis[k] =false; //右子树为不选择该节点
rsum-=a[k];
dfs(k+1);
rsum+=a[k];
}
return ;
}
int main(){
IOS;
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>a[i];
rsum+=a[i]; //提前把rw存下并计算出来
}
dfs(1); //对第一个数的状态进行搜索
cout<<"No Solution";
//特判方式：找到解就在 函数中找到解的时候return掉整个程序
//没找到就会跳出来执行最后的特判
return 0;
}
2.最小重量机器设计
#include <iostream>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=110;
int res=0x3f3f3f3f;
int n,m,k,c[N][N],w[N][N];
int csum,wsum;
int s[N]; //记录 在选择的过程中每一行选择了第几个数
int ans[N]; //记录 在最后的答案中每一行选择了第几个数
void dfs(int t){
if(t==n+1){
if(wsum<res){
res=wsum;
for(int i=1;i<=n;i++) ans[i]=s[i];
}
return ;
}
for(int j=1;j<=m;j++){ //遍历每一个供应商
s[t]=j;
csum+=c[t][j],wsum+=w[t][j];
if(csum+c[t][j]<=k&&wsum+w[t][j]<res) dfs(t+1);
//判断是否超过和剪枝 满足条件才进入下一层搜索树 不满足则直接剪枝
csum-=w[t][j],wsum-=w[t][j]; //恢复状态
}
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>c[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
dfs(1);
cout<<res<<endl;
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}
3.无和集
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e5+5;
int n,m,k;
void solve(int n){
vector<vector<int>> v(n);
int k=1; //从1开始搜索答案
while(true){
bool CanAdd=false; //记录是否可以将现在的k加入到某个无知集中
for(int i=0;i<n;i++){ //遍历每个无知集
bool conflict=false; //检查是否可以
//遍历某个集合中所有的数 双层循环搜索一遍 看是否会该集合发生冲突
for(int t=0;t<v[i].size();t++){
for(int j=t+1;j<v[i].size();j++){
if(v[i][t]+v[i][j]==k) {
conflict=true;
break;
}
}
}
//若检索某个集合中发现没有冲突 就将现在的k加入该集合中 并标记当前的k可以加入到某个无知集 退出要放入无知集的循环的搜索
if(!conflict){
v[i].push_back(k);
CanAdd=true;
break;
}
}
if(!CanAdd) break; //若某次遍历后发现无法将k加入到该集合中 则说明在当前开辟的n个vector集合中 无法承载下k个值
k++;
}
k--; //现在的k是刚好不能放下的边界 所以再减减一次
cout<<k<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<v[i].size();j++) {
cout<<v[i][j]<<" ";
}
cout<<endl;
}
}
int main(){
cin>>n;
solve(n);
return 0;
}4.工作分配问题
#include <iostream>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=1e3+5;
int n,m,a[N][N];
int sum,res=0x3f3f3f3f;
bool vis[N]; //标记第i个工作是否有人做了
void dfs(int k){ //为第k个人安排工作
if(k==n+1){
res=min(res,sum);
return ;
}
for(int j=1;j<=n;j++){
if(!vis[j]){
sum+=a[k][j];
vis[j]=true;
if(sum<res) dfs(k+1);
sum-=a[k][j];
vis[j]=false;
}
}
}
int main(){
IOS;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
dfs(1);
cout<<res<<endl;
return 0;
}5.最佳调度
#include <iostream>
#include <cstring>
#include <algorithm>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
using namespace std;
const int N=110,INF=0x3f3f3f3f;
int n,m;
int a[N],sum[N],res=INF;
//搜索树第i层为第i个任务 枚举放到每一个流水线
//优化搜索顺序 排序
// 最优化 已经超过答案
//排除等效冗余 可跳过相同时间的流水线
//因为即使相同 也还要累加 所以不能跳过任务
void dfs(int u,int ans){
if(ans>=res) return ; //最优化剪枝
if(u==n) { //终止条件
res=ans;
return ;
}
for(int i=0;i<m;i++){
if(i<m-1&&sum[i]==sum[i+1]) continue; //排除等效冗余
sum[i]+=a[u];
dfs(u+1,max(ans,sum[i]));
sum[i]-=a[u];
}
return ;
}
int main(){
IOS;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n); //优化搜索顺序
reverse(a,a+n);
dfs(0,0);
cout<<res<<endl;
return 0;
}