如何从算法上优化此代码？将 N 个科目分配给 N 个学生的方法有多少种？

Question

Your task will be to calculate number of different assignments of n different topics to n students such that everybody gets exactly one topic he likes.

Each test case begins with number of students n (1<=n<=20). Each of the next n lines contains n integers describing preferences of one student. 1 at the ith position means that this student likes the ith topic, 0 means that he definitely doesn't want to take it.

我通过定义 DP[i][掩码] 来表示仅使用 i 个元素形成掩码集的方法的数量来解决这个问题！

这里的 mask 是 Subjects 的一个子集，它告诉我有多少科目被选修了。

重复是

for(i=1;i<N;i++)    //Student
    for(j=1;j<(1<<N);j++)   //Subject Subset
    {
        for(k=0;k<N;k++)        //Selecting subject
            if( (j&(1<<k)) && A[i][k] )
                DP[i][j]+=DP[i-1][j^(1<<k)];
    }

即从第 i 个学生最喜欢的科目中选出一个科目并递归到较低的状态!!

但是，这还不够，因为解决方案的复杂度为 O(2^N * N^2)。

我们至少要打倒一个N！

如何降低这个问题的复杂性？这是我的代码：

#include<bits/stdc++.h>
using namespace std;
long long DP[20][(1<<20)+1];
int main()
{
    int T;
    scanf("%d",&T);
    for(;T;--T)
    {
        int N,i,j,k;

        scanf("%d",&N);

        int A[N+1][N+1];

        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                scanf("%d",&A[i][j]);
        /*

        First of all let's think about the state!!
        DP[i][j] where i is the i th student I am considering j is a bitmask which tells me which all subjects are
        Done!!
        ********All Right************
        So what can the recurrence be..?
        traverse over the array A[i][]
        If We can use the k th element of i.e A[i][k].
        We need to try assigning it and Get the number of ways
        *********Seems Fine *********
        What will be the base case??
        When only one element left in the mask and i is 1 we won't traverse more down!!

        **OK**
        SO what is the topological order of DP states !>>>????

        I dont Know!! Let's think... Let me explain ummmmmmmmmmmmmmmmmmmmmmmmmmmm
        ummmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm
        I am like calling a smaller i with smaller subset!
        for every i
            go in the order of increasing subsets

        I think that should work!! Let's see
        */
        for(i=0;i<(1<<N);i++)
            DP[0][i]=0;
        for(i=0;i<N;i++)
                    if(A[0][i])
                        DP[0][1<<i]=1;

        for(i=1;i<N;i++)    //Student
            for(j=1;j<(1<<N);j++)   //Subject Subset
            {
                DP[i][j]=0;
                for(k=0;k<N;k++)        //Selecting subject
                    if( (j&(1<<k)) && A[i][k] )
                        DP[i][j]+=DP[i-1][j^(1<<k)];
            }
        long long ans=0;

        for(i=1;i<(1<<N);i++)
            ans+=DP[N-1][i];
        printf("%lld\n",ans);
    }
    return 0;
}

问题 Link 如果您需要它：Spoj

Answer 1

您可以使用两种技术来降低时间复杂度：

中途相遇
一口气搜索

所以，我们注意到，对于第 i 个人，我们不需要设置所有 n 位，而只需要设置 i 位，而不是遍历从 (0 到 2^n) 的所有数字)，我们只需要遍历所有设置了 i 位的数字。我们可以使用 BFS

其次，如果我们使用一个数组dp存储将受试者分配给前一半n/2人的方法数，另一个数组dp1存储方法数给后半n/2人分配科目，所以给n个人分配科目的方法数是

int x = a number that has n/2 bit set

int result = sum (dp[x] + dp1[2^n - 1 - x]);

时间复杂度为 C(n, n/2)*n/2*n，n = 20 ~ 3*10^7 次操作。

Answer 2

您可以通过对内部循环进行一些黑客微优化来提高速度（在我的计算机上，在最坏的情况下输入速度提高了 3.7 倍）。

想法是给定一个二进制数，例如 10100，您可以通过操作 10100 & -10100 = 00100 提取单个设置位。

因此，我们可以使用以下代码将对 k 的循环更改为仅对重要位进行循环：

#include<bits/stdc++.h>
using namespace std;
long long DP[20][(1<<20)+1];
int main()
{
    int T;
    scanf("%d",&T);
    for(;T;--T)
    {
        int N,i,j,k;
        int masks[20];           // ADDED

        scanf("%d",&N);

        int A[N+1][N+1];

        for(i=0;i<N;i++) {
            masks[i] = 0;
            for(j=0;j<N;j++) {
                scanf("%d",&A[i][j]);
                masks[i] |= A[i][j]<<j; // ADDED
            }
        }

        for(i=0;i<(1<<N);i++)
            DP[0][i]=0;
        for(i=0;i<N;i++)
                    if(A[0][i])
                        DP[0][1<<i]=1;

        for(i=1;i<N;i++)    //Student
            for(j=1;j<(1<<N);j++)   //Subject Subset
            {
                long long t = 0;           // ADDED
                int mask = j & masks[i];   // ADDED
                while(mask) {              // ADDED
                  int bit = mask & -mask;  // ADDED
                  t += DP[i-1][j - bit];   // ADDED
                  mask -= bit;             // ADDED
                }                          // ADDED
                DP[i][j]=t;                // ADDED
            }
        long long ans=0;

        for(i=1;i<(1<<N);i++)
            ans+=DP[N-1][i];
        printf("%lld\n",ans);
    }
    return 0;
}

Answer 3

嗯，我发现我们可以更快地解决问题！这是怎么回事！！我们不需要处理 i 循环！为什么？？如果一个掩码包含 i 位，那么只有它可以为我们提供一些方法来做，否则它是零，因为一个主题要分配给每个人！所以现在，重复周期变为

for（每个位掩码）获取掩码的位数！（这是唯一与掩码关联的 i）。由于上述论点，每个掩码仅与一个 i 相关联！！

检查我们可以通过给学生所有有利的科目来达到当前状态的所有方式！现在它将导致较低位数的掩码，它也与唯一的 i 相关联，特别是 i-1 !

所以现在，这很好，我们可以在这种情况下进行一维 DP...

for(j=1;j<(1<<N);j++)   //Subject Subset
     {
            DP[j]=0;
            i=__builtin_popcount(j);
            for(k=1;k<=N;k++)        //Selecting subject
                if( (j&(1<<(k-1))) && A[i][k] )
                        DP[j]+=DP[j^(1<<(k-1))];
    }

我的 AC 代码（运行时间 0.78）通过预处理位计数而不是 __builtin_popcount()

进行了改进

#include<bits/stdc++.h>
using namespace std;
long long DP[(1<<20)+1];
int main()
{
    int T;
    scanf("%d",&T);
    for(;T;--T)
    {
        int N,i,j,k;

        scanf("%d",&N);

        int A[N+1][N+1];

        for(i=1;i<=N;i++)
            for(j=1;j<=N;j++)
                scanf("%d",&A[i][j]);


        for(i=0;i<(1<<N);i++)
            DP[i]=0;
        DP[0]=1;

        for(j=1;j<(1<<N);j++)   //Subject Subset
             {
                    DP[j]=0;
                    i=__builtin_popcount(j);
                    for(k=1;k<=N;k++)        //Selecting subject
                        if( (j&(1<<(k-1))) && A[i][k] )
                                DP[j]+=DP[j^(1<<(k-1))];
            }

        long long ans=0;
        printf("%lld\n",DP[(1<<N)-1]);
    }
    return 0;
}

与@Peter 的优化代码相比。他能够优化它以通过时间限制运行 spoj 测试数据的时间 2.60 秒！

#include<bits/stdc++.h>
using namespace std;
long long DP[20][(1<<20)+1];
int main()
{
    int T;
    scanf("%d",&T);
    for(;T;--T)
    {
        int N,i,j,k;
        int masks[20];           // ADDED

        scanf("%d",&N);

        int A[N+1][N+1];

        for(i=0;i<N;i++) {
            masks[i] = 0;
            for(j=0;j<N;j++) {
                scanf("%d",&A[i][j]);
                masks[i] |= A[i][j]<<j; // ADDED
            }
        }

        for(i=0;i<(1<<N);i++)
            DP[0][i]=0;
        for(i=0;i<N;i++)
                    if(A[0][i])
                        DP[0][1<<i]=1;

        for(i=1;i<N;i++)    //Student
            for(j=1;j<(1<<N);j++)   //Subject Subset
            {
                long long t = 0;           // ADDED
                int mask = j & masks[i];   // ADDED
                while(mask) {              // ADDED
                  int bit = mask & -mask;  // ADDED
                  t += DP[i-1][j - bit];   // ADDED
                  mask -= bit;             // ADDED
                }                          // ADDED
                DP[i][j]=t;                // ADDED
            }
        long long ans=0;

        for(i=1;i<(1<<N);i++)
            ans+=DP[N-1][i];
        printf("%lld\n",ans);
    }
    return 0;
}

如何从算法上优化此代码？将 N 个科目分配给 N 个学生的方法有多少种？

How to optimise this code Algorithmically? Number of ways to assign N subjects to N students?

c++

algorithm

optimization

dynamic-programming