SDUT《 算法分析与设计》 实验四-搜索算法

• A - 子集和问题
• B - 运动员最佳匹配问题
• C - 工作分配问题
• D - 整数变换问题

#include 
#include
#define ll long long
const int N = 1e5 + 10;
using namespace std;

int n,c;
int a[N];
int sum=0;
bool st[N];

void DFS(int x){
    if(sum>c) return ;
    if(x>n) return ;
    st[x]=1;
    sum+=a[x];
    if(sum==c){
        bool tag=0;
        for(int i=1;i<=x;i++){
            if(st[i]){
                if(!tag) tag=1;
                else cout<<" ";
                cout<>n>>c;
    int su=0;
    for(int i=1;i<=n;i++) cin>>a[i],su+=a[i];
    if(su 
B - 运动员最佳匹配问题 
#include 
#include
#define ll long long
const int N = 25;
using namespace std;

int n;
int p[N][N];
int q[N][N];
int g[N][N];
int mg[N];
int maxn=INT_MIN;
int sum=0;
bool st[N];

void DFS(int x){
    //cout<n){
        maxn=max(maxn,sum);
        return ;
    }
    int cnt=0;
    for(int i=x;i<=n;i++) cnt+=mg[i];
    if(sum+cnt>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>p[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>q[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            g[i][j]=p[i][j]*q[j][i];
            mg[i]=max(mg[i],g[i][j]);
        }
    }
    DFS(1);
    cout< 
C - 工作分配问题 
#include 
#include
#define ll long long
const int N = 25;
using namespace std;

int n;
int mp[N][N];
int minn=INT_MAX;
int sum=0;
bool st[N];

void DFS(int x){
    if(x>n){
        minn=min(minn,sum);
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            st[i]=1;
            sum+=mp[i][x];
            if(sum<=minn) DFS(x+1);
            st[i]=0;
            sum-=mp[i][x];
        }
    }
}

inline void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>mp[i][j];
        }
    }
    DFS(1);
    cout< 
D - 整数变换问题 
#include 
#include
#define ll long long
const int N = 1e5 + 10;
using namespace std;

int n,m;
int tot=1;
bool st[N];
string s="";

bool DFS(int x,int num){
    if(x>tot) return 0;
    if(num==m) return 1;
    auto temp=num;
    for(int i=0;i<2;i++){
        if(!i) temp=num*3;
        else temp=num/2;
        if(DFS(x+1,temp)){
            if(!i) s+='f';
            else s+='g';
            return 1;
        }
    }
    return 0;
}

inline void solve(){
    cin>>n>>m;
    while(!DFS(0,n)) tot++;
    cout<