I have a set $R$ of requirements that have to be fulfilled with a certain amount of "points", and a set $E$ of entries that can fulfill multiple requirements with a certain amount of "points" each.
For example: In order to get your degree, you have to acquire 50 credits in Mathematics, 20 credits in Physics and 10 credits in Philosophy. You also have a set of lectures that you have visited, while one lecture can be assigned to one or more subjects, and has a certain amount of credit points (e.g "Philosophy of Science" gives 5 Philosophy credits and 3 Physics credits).
Now, let us assume you have completed enough lectures to get your degree (but way more than necessary). Let us also assume that your university is greedy and getting a completed exam accredited on your final report always costs a fixed amount of money. From all the lectures, how do you get a subset $E' \subseteq E$ of completed lectures such that all requirements in $R$ are fulfilled and $|E'|$ is minimal?
I have started by modelling the problem as a weighted bipartite graph of two disjoint vertex sets $R \cup E$. If some $e \in E$ fulfills a requirement $r \in R$ with $p$ credits, an edge of weight $p$ is drawn between $e$ and $r$. Also, each $r \in R$ is weighted (as a vertex) with the amount of credits needed to fulfil it.
We are looking for a minimal subset $E' \subseteq E$ such that for each $r \in R$, the sum of weights of edges from $$r_{E'}^+ = \{e \in E' | e \text{ is connected to } r\}$$ is greater or equal than the weight of $r$ itself. This is done assuming such an $E'$ exists.
As you see, I have worked the modelling out, but am at a loss when it comes to some kind of solution. It looks like some mix of a matching and flow problem to me, but this is unlike any problem I have seen. All help is appreciated.
Hint: Your modelling of the problem makes sense. This is an instance of the assignment problem, or minimum weight matching problem for which a polynomial time algorithm exists.