2022寒假集训day3

day3：四道检测题，花了大半天时间。

子集和问题

问题描述

子集和问题的一个实例为<S,c>。其中S={x1,x2,…,xn}是一个正整数的集合，c是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中所有元素的和为c

找不到原题了

#include <bits/stdc++.h>

using namespace std;

int n,a[10000000],b[10000000];

int m,i,k=1,s=0;

bool f[10000000];

void print(int k)

{

    for (i=1;i<=k;++i)cout<<b[i]<<" ";

    exit(0);

} 

void search(int k,int s,int m)

{

    int i;

    if (s>m)return;

    if (k>n){cout<<"No Solution!";exit(0);}

    for (i=1;i<=n;++i)

    if (f[i])

    {

        f[i]=false;

        s=s+a[i];

        b[k]=a[i];

        if (s==m){print(k);}

          else search(k+1,s,m);

        s=s-a[i];

            f[i]=true;

            b[k]=0;

    }

    return ;

}

int main()

{

    cin>>n;    cin>>m;

    for (i=1;i<=n;++i)

        cin>>a[i];

    for (i=1;i<=n;++i)

        f[i]=true;

    search(k,s,m);

    return 0;

}

坑很多啊，除了不要忘记无解，而且No,Solution的S 也需要大写，就无语。硬是卡了很长时间，去做后面的题

这道题大体就是对集合的整体先搜索一遍，然后选取某几个元素与定值相等，并输出这几个元素。

————————————————————————————————————————

工作分配问题

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为 c i j c_{ij} cij。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。
设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

Input
输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。
Output
将计算出的最小总费用输出。

#include <bits/stdc++.h>

using namespace std;

#define N 1000

int cost[N][N];

int b[N]={0};

int n;

int sum;

void search(int i,int c)

{

     if(c>sum) return;

     if(i==n) {

         if(c<sum) sum=c;

         return;

     }

     for(int j=0;j<n;j++) {

         if(b[j]==0) {

             b[j]=1;

             search(i+1,c+cost[i][j]);

             b[j]=0;

         }

     }

 }

 int main()

 {

     cin>>n;

     for(int i=0;i<n;i++) {

        for(int j=0;j<n;j++) {

             cin>>cost[i][j];

         }

     }

         sum = N;

         search(0,0);

          cout<<sum;

          return 0;

 }

T2就是我写起来相对得心应手的一题了，在T1上死磕之后看到它显得无比亲切。

虽然之前做过类似的，整体思路还算清楚，写起来也还是有些犹豫。尤其是中间的search，和T1的不同，而是类似全部枚举再进行比较。

————————————————————————————————————————

装载问题

题目描述
有一批共 n 个集装箱要装上艘载重量为 c 的轮船，其中集装箱 i 的重量为 wi 。找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。
输入

第一行有2个正整数n和c。n是集装箱数，c是轮船的载重量。第2行中有n个正整数，表示集装箱的重量（0<n<10000,0<c<32767)。
输出
计算出的最大装载重量输出。

#include<bits/stdc++.h>
using namespace std;
int maxx,ans,n,c,sz[10000];
void search(int i,int k=0) {
    if(maxx>c) return ;
    if(k==i+1) {
        ans=max(ans,maxx);
        return ;
    }
    if(maxx+sz[k]<=c) {
        maxx+=sz[k];
        search(i,k+1);
        maxx-=sz[k];
    }
    search(i,k+1);
}
int main() {
    cin>>n>>c;
    for(int i=1; i<=n; i++) 
        cin>>sz[i];
    sort(sz+1,sz+n+1);
    search(n);
    cout<<ans<<endl;
    return 0;
}

困扰了很长时间，虽是第三题但却是最后一个做出来的。

尽可能的去寻找最大的重量使船尽可能的装满。

首先读题不仔细，应该把整道题全部读懂并且有具体思路之后在写代码，而不是边想边写，会使效率低下，并且一直困扰在一个位置。

————————————————————————————————————————

字符序列

从三个元素的集合[A，B，C]中选取元素生成一个N个字符组成的序列，使得没有两个相邻字的子序列（子序列长度=2）相同。例：N = 5时ABCBA是合格的，而序列ABCBC与ABABC是不合格的，因为其中子序列BC，AB是相同的。
对于由键盘输入的N(1<=N<=12)，求出满足条件的N个字符的所有序列和其总数。
测试数据：
输入：4
输出：72

#include <bits/stdc++.h>

using namespace std;

int n,sum=0;

int ans[15];

bool pd()

{

    int cnt=0;

    for(int i=3; i<=n; i++)

    {

        if(ans[i]==ans[i-2])

            cnt++;

        else cnt=0;

        if(cnt==2)

           return 0;

    }

   return 1;

}

void dfs(int x)

{

    if(x==n+1)

    {

        if(pd())

            sum++;

        return;

    }

    for(int i=1;i<=3;i++)

    {

        ans[x]=i;

        dfs(x+1);

    }

}

int main()

{   scanf("%d",&n);

    dfs(1);

    printf("%d",sum);

   return 0;;

}

前面一直在用search，这道就换成深搜了。

思路还算清晰，很快就qie掉了。

本日总结：

search掌握不算太熟练，做题分析不到位，细节浪费很长时间。

对一些算法也进行了强化，但还是有所欠缺，多加练习。

巴特西

2022寒假集训day3

问题描述

最新文章

热门文章