Is there a dynamic programming solution to the student allocation problem? The student project allocation problem I am trying to solve goes as follows.


There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
Each student makes a top $3$ of their preferred projects.
Each student should be allocated to exactly one project.
Each project has a maximum number of students which can choose it, $c$.


We want to find some combination of students being allocated to projects so that a maximum of students are allocated their preferred project. Of the students who didn't get their preferred choice, a maximum of them should be allocated their second choice.

This is a optimization problem with constraints. If we assign a priority weight $w_{ij}$ for the $i^{th}$ student choosing the $j^{th}$ project, where $w_{ij} \in \{0, 1, 2, 3\}$, and $w_{ij}$ is $0$ when the student $i$ did not include project $j$ in his top $3$, $1$ if it is his third choice, $2$ second choice, $3$ preferred choice.

We can also introduce a variable $x_{ij} \in \{0, 1\}$, which is equal to $1$ when student $i$ has been allocated to project $j$ and $0$ otherwise.

Now we can formulate an objective function, $o$, to maximize in order to reach an optimal allocation.

$$o = \sum_{\forall (i, j) \in S \times P}{x_{ij} \cdot w_{ij}}$$

We must maximize $o$ according to the problems constraints.

$$\forall i \in S : \sum_{\forall j \in P}{x_{ij}} = 1 \quad \textrm{every student is allocated to exactly one project}$$

$$\forall j \in P : \sum_{\forall i \in S}{x_{ij}} \leq c_j \quad \textrm{no project is allocated more than its maximum number of students}$$

I think there are no other constraints. 

Now, I am stuck. How do I go about actually solving this on a computer given all of the above. Is there a relationship between the optimal allocation for $i$ students and $i + 1$ students? Can I use dynamic programming, and if so how? Or do I have to use some other method, and if so what method?
This sounds like it could be solved using a flow network.

Define the graph $G=(V,E)$ such that:


Add a starting node $s$. It will be the "source" node in the flow-graph.
Add a node $v_{s_i}$ for every student $s_i$.
Add a node $v_{p_j}$ for every project $p_j$.
Add the final node $t$. It will be the "sink" node for the flow-graph.


Now, start adding the edges and their weights as following:


For every $s_i\in S$, add an edge $(s,v_{s_i})$ of weight 1.
For every $s_i\in S$ and every preferred project of his, $p_j$, add an edge $(v_{s_i},v_{p_j})$ with weight 1.
Finally, for every project $p_j$ add an edge $(v_{p_j},t)$ of weight $c$.


Run the Ford Fulkerson algorithm on this graph $G$ we defined, and it will spit out an integer flow $f$. Assign a student $s_i$ to project $p_j$ if there is flow between $v_{s_i}$ and $v_{p_j}$ in $f$. Notice there might be students that wont be assigned anything in that way. They cannot be assigned to anything they prefer - so just assign them in any free project.

This algorithm runs in time $\mathcal O(|S||P|)$ since $|V|=\mathcal O(|S|+|P|)=\mathcal O(|P|)$, and each student has up to 3 preferred project so $|E|=\mathcal O(|V|)=\mathcal O(|P|)$ as well and the value of $f$, $|f|\le|S|=O(|S|)$.

It also provides the best possible solution, since it always maximizes the flow's value which is the number you want to maximize (think why).