1.24测试题summary

1.子集和问题

这个题有多个解，但题面没有明确说出需要哪组解。

此题最大不同是搜索的终止条件可以变化

注意优化，把不需要搜索的数据判断出来，直接给出No Solution的答案！

#include
#define enter printf("\n")
using namespace std;
int s[10000],a[10000],sum[10000]; //原集合，子集合 
int n,c;
void print(int l){
    for(int i = 1;i < l;i++){
        printf("%d ",a[i]);
    }
    enter;
    exit(0);
}
void dfs(int x,int k,int tot){    //子集中元素个数，当前取第几个元素，当前元素和  
    if(tot == c) {
        print(k);
    }
    if(tot > c) return;
    if(tot+sum[x]return;
    for(int i = x;i <= n;i++){   //不能重复取 
        a[k] = s[i];  // save
        dfs(i+1,k+1,tot+s[i]);
    }
}
int main(){
    cin>>n>>c;
    for(int i = 1;i <= n;i++){
        scanf("%d",&s[i]);
    }
    for(int i = n;i > 0;i--){
        sum[i]=sum[i+1]+s[i];
    }
    if(sum[1]>=c) dfs(1,1,0);
    printf("No Solution!");
    return 0;
}

2.分配工作

n个人选n项工作的一种，各不相同，求最小费用

从题意就能推出要用深度搜索的，核心代码没问题，但是超时只得80分，后面调了很久，代码各种优化

其实关键部分还是总费用比当前最小费用大就结束，不需要往下推，因为求的是最小

#include
using namespace std;
bool b[21]; //第i项工作是否分配？1：0
int t[21][21];
void search(int n,int k,int w){  //第k个人要分配工作 ,总费用 
    if(k > n){
        if(w < t[0][0]){
            t[0][0] = w;
        }
        return;
    }
    if(w > t[0][0]) return;
    for(int j = 1;j <= n;j++){
        if(!b[j]){
            b[j] = 1;
            search(n,k+1,w+t[k][j]);
            b[j] = 0;
        }
    }
}
int main(){
    int n;
    t[0][0] = 10000;
    cin>>n;
    for(int i = 1;i <= n;i++){  //i行表示第i个人 
        for(int j = 1;j <= n;j++){  //j列表示第j项工作费用 
            scanf("%d",&t[i][j]); 
        }
    }    
    search(n,1,0);
    printf("%d",t[0][0]);
    return 0;
}
/*
3
4 2 5
2 3 6
3 4 5
4.339s--1.102s
*/

3.load负载问题

求最靠近载重量的组合，这个和拔河问题异曲同工，不过不知道是不是搜索的算法用时过长，最后还是没ac，以下是搜索算法。

（可能条件判断还能再优化一下）

#include
using namespace std;
int w[200],maxk = 0;
bool b[200];
void search(int n,int c,int k,int z,int q){  //n,c,货物数，总重 ,前一个货物 
    for(int i = q+1;i <= n;i++){
        if(b[i]) continue;
        if(z+w[i]>c){
            if(z > maxk) maxk = z;
            continue;
        }
        b[i] = 1;
        search(n,c,k+1,z+w[i],i);
        b[i] = 0;
    }
}
int main(){
    int n,c,sum=0;
    scanf("%d %d",&n,&c);
    for(int i = 1; i <= n;i++){
        scanf("%d",&w[i]);
        sum+=w[i];
    }
    if(sum<c){
        printf("%d",sum);
        return 0;
    }
    search(n,c,1,0,0);
    printf("%d",maxk);
    return 0;
}

就在刚才！终于调过了！！

代码如下

之前的错误是用b[i]和q双重方式来解决互斥的问题，自己还没注意到，现在做了关键性的精简，甚至循环里只有一句，整个搜索精简到四行！

#include
using namespace std;
int w[200],maxk = 0;
int n,c;
void search(int z,int q){  //货物数，总重 ,前一个货物 
    if(z>c) return;
    if(z>maxk) maxk=z;
    for(int i = q+1;i <= n;i++){
        search(z+w[i],i);
    }
}
int main(){
    int sum=0;
    scanf("%d %d",&n,&c);
    for(int i = 1; i <= n;i++){
        scanf("%d",&w[i]);
        sum+=w[i];
    }
    if(sum<c){
        printf("%d",sum);
        return 0;
    }
    search(0,0);
    printf("%d",maxk);
    return 0;
}

4.字符序列

给定字符序列长，在｛A,B,C｝元素中选择元素来构成，要求相邻的两个2字符子序列不能相同。这题一开始理解错了按照不必相邻的情况写的，后面改过来，做得还算顺利

#include
using namespace std;
int n,ans;
int a[14];
bool mycmp(){
    for(int i = 1;i <=n - 3;i++){
        if(a[i]==a[i+2]&&a[i+1]==a[i+3]) return 0;
    }
    return 1;
}
void search(int pos){ 
    if(pos>n){
        if(mycmp()){
            ans++;
        }
        return;
    }
    for(int i = 0;i < 3;i++){
        a[pos] = i;
        search(pos+1);
        a[pos] = 0;
    }
}
int main(){
    cin>>n;
    search(1);
    printf("%d",ans);
    return 0;
}