Блог

В хакатоне по кодированию у меня возникла следующая проблема :

Существует K классов, каждый из которых обладает определенной емкостью. Есть N студентов, и у каждого есть одно или два предпочтения в классе. Нам нужно напечатать «ДА», если все учащиеся могут быть распределены в класс, или «НЕТ».

Например :

 
N = 4
K = 3
capacity = {2,1,1}
preference = {"0","0,2","1","2"}

 

Есть 4 студента и 3 класса, и в соответствии с их предпочтениями могут быть выделены следующие классы:

Таким образом, ответом на вышеприведенный сценарий будет «ДА»

Каков будет алгоритм подхода к решению вышеуказанной проблемы?

Обновить:

Я использовал объяснение Кристиана ниже, чтобы придумать следующее решение:

 import java.util.*;
public class StudentAllocation{

    public static void main(String args[]){
        int N = 4;
        int K = 3;
        int capacity[] = {2,1,1};
        String preference[] = {"0","0,2","1","2"};
        System.out.println(canAllocate(N,K,capacity,preference));
    }
    public static String canAllocate(int N,int K,int c[],String p[]){
        //Creating nodes for each student and capacity*class
        //Also making one node for source and on node for sink
        HashMap<String,Integer> nm = new HashMap<String,Integer>();
        int n = 1;
        for(int i = 0;i < N;i  ){
            nm.put("s" i,n  );
        }
        for(int i = 0;i < c.length;i  ){
            for(int j = 0;j < c[i];j  ){
                nm.put("c" i j,n  );
            }
        }
        n = n 1;
        int[][] g = new int[n][n];
        //connecting source to all student nodes
        for(int i = 1;i <= N;i  ){
            g[0][i] = 1;
        }
        //connecting all capacity*class nodes to sink
        for(int i = N 1;i < n-1;i  ){
            g[i][n-1] = 1;
        }
        //Connecting student node to all the capcity node of class of his preference
        for(int i = 0;i < p.length;i  ){
            String ps = p[i];
            String pst[] = ps.split(",");
            for(int j = 0;j < pst.length;j  ){
                for(int k = 0;k < c[Integer.parseInt(pst[j])];k  ){
                    g[nm.get("s" i)][nm.get("c" pst[j] k)] = 1;
                    g[nm.get("s" i)][nm.get("c" pst[j] k)] = 1;
                }
            }
        
        }
        //Using Ford Fulkerson to callculate max flow
        // If max flow is equal to no of students then each student can be allocated to any class of his preference
        //Making residual graph
        int rg[][] = new int[n][n];
        
        for(int i = 0;i < n;i  ){
            for(int j = 0;j < n;j  ){
                rg[i][j] = g[i][j];
            }
        }
        
        int parent[] = new int[n];
        int max_flow = 0;
        int count = 0;
        while(bfs(rg,0,n-1,parent)){
            count  ;
            
            int path_flow = Integer.MAX_VALUE;
            for(int i = n-1;i != 0;i = parent[i]){
                path_flow = Math.min(path_flow,rg[parent[i]][i]);
            }
            
            max_flow = max_flow   path_flow;
            for(int i = n-1;i != 0;i = parent[i]){
                rg[parent[i]][i] -= path_flow;
                rg[i][parent[i]]  = path_flow;
            }
            
        }
        if(max_flow == N){
            return "YES";
        }
        return "NO";    
        
    }
    
    public static boolean bfs(int rg[][],int u, int v, int[] p){
        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
        q.offer(u);
        int marked[] = new int[rg.length];
        while(!q.isEmpty()){
            u = q.poll();
            marked[u] = 1;

            for(int i = 0;i < rg[u].length;i  ){
                if(marked[i] != 1 amp;amp; rg[u][i] > 0){
                    p[i] = u;
                    q.add(i);
                    if(i == v){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    
}

 

Вы можете создать двудольный граф с узлами учащихся на одной стороне, а затем на другой стороне создать узлы емкости класса*. Каждый узел представляет одну точку в классе.

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

Тогда проблема заключается в том, чтобы найти идеальное соответствие в этом графике. Если такое соответствие существует, это «ДА», если нет, это «НЕТ».

Вот рекурсивный алгоритм. Мы рассматриваем последнего студента, пробуем его первый выбор и проверяем, может ли быть решена проблема для оставшихся n-1 студентов. Если нет, попробуйте второй вариант (если есть), и снова проверьте проблему для оставшихся учеников.

Вот реализация на PHP (вы можете протестировать ее здесь):

 <?php
function isSolvable($choices1, $choices2, $capacities, $n)
{
    if($n==0)
        return true; // No students left to allocate

    // First choice of student $n
    $c1 = $choices1[$n-1];
    if($capacities[$c1]>0)
    {
        $capacities[$c1]--;
        if(isSolvable($choices1, $choices2, $capacities, $n-1))
            return true;
        $capacities[$c1]  ;
    }

    // Second choice of student $n
    $c2 = $choices2[$n-1];
    if($c2>=0 amp;amp; $capacities[$c2]>0)
    {
        $capacities[$c2]--;
        if(isSolvable($choices1, $choices2, $capacities, $n-1))
            return true;
    }

    return false;
}

$choices1 = [0, 0, 1, 2];
$choices2 = [-1, 2, -1, -1];
$capacities = [2, 1, 1];
echo isSolvable($choices1, $choices2, $capacities, count($choices1)) ? 'YES' : 'NO';
?>