Алгоритм динамического программирования для задания задач

Question

Я борюсь с этой проблемой.Я пытался решить это с помощью простой рекурсии, но время, которое требуется для больших случаев, огромно, и я хотел бы улучшить его, написав алгоритм динамического программирования.

Есть n заданных учеников и n заданных заданий.Каждый студент представлен 1d array of length n из 0 с и 1 с.A[i] == 0 означает, что этот ученик не может выполнить i 'задачу, а A[i] == 1 означает, что этот ученик может выполнить i' задачу.Цель состоит в том, чтобы определить, сколько существует различных способов назначения заданий учащимся таким образом, чтобы все задания могли быть выполнены, и один ученик выполнил только одно задание.

Буду признателен за любые советы о том, как подходить к этой проблеме динамическим способом программирования.

Answer 1

    cin>>n;
    int a[n+1][n+1];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            cin>>a[i][j];
        }
    int dp[(1<<n)];
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(mask=1;mask<(1<<n);mask++){
        x=getbits(mask);
            for(i=0;i<n;i++)
                if(mask & (1<<i) && a[x][i+1]){
                    dp[mask]+=dp[mask^(1<<i)];
            }
    }
    cout<<dp[(1<<n)-1];

Условием инициализации является dp [0] = 1
, поэтому состояние dp - (маска), где x обозначает, что человеку до x была назначена задача, которая также равна заданным битам маски, имаска - это двоичное число, каждый бит которого представляет, была ли назначена эта задача.

, если i-й бит не установлен и x-й человек может выполнить эту работу

    dp[mask]+=dp[mask^(1<<i)];

Сложность времени равна O (N * 2 ^ N), а сложность пространства O (2 ^ N)

Answer 2

Ваша проблема действительно похожа на проблему соответствия с двудольным графом (Теория графов), где студент - это узел, а задача - другая (из другого ансамбля).Края представляют совместимость между ними.Я не имею в виду никакого решения, но вы сможете найти некоторые полезные сведения о сопоставлении проблем и динамическом программировании.