title: Maximize sum of values of K courses if all prerequisites must be met
body: <p>Background: The following problem occurred to me when I was trying to come up with a hiring challenge for software engineers in my company. I quickly realized that it was probably too difficult since I couldn't come up with a good solution myself :-) Still, I would be interested to know if somebody else can think of an efficient algorithm.</p>
  <p>Consider a worker who is deciding which of a selection of continuing education courses to take. Each course will teach them a skill, which will boost their salary by a certain known amount. The worker wants the maximum salary boost, but there are some constraints to consider: Each course takes a month to complete, and the worker can only take one course at a time. They only have K months available for their education. Furthermore, some courses have prerequisites and can only been taken if the worker already completed all of the prerequisite courses. How can the worker find the curriculum that will give them the maximum raise?</p>
  <p>More formally, consider a directed acyclic graph with N nodes, which have values v[0], ..., v[N-1] (all positive), and a list of M directed edges E = [(a[0],b[0]), ..., (a[M-1],b[M-1])]. For simplicity we can assume topological order (i.e. 0 &lt;= a[i] &lt; b[i] &lt; N for i = 0, ..., M-1). What is the maximum sum of values of K nodes if we can only select a node if all of its ancestors in the DAG have been selected?</p>
  <p>We can trivially solve this problem in O(M + K * N^K) by looping over all size-K subsets and checking if all prerequisites are met. A simple Python implementation would be as follows:</p>
  <pre><code>def maxSumNodes(v, E, K):
      # For each node, compute all of its direct ancestors in the DAG
      N = len(v)
      ancestors = [[] for i in range(N)]
      for a, b in E:
          ancestors[b].append(a)
      maxSumValues = 0
      for r in itertools.combinations(range(N), K):
          sumValues = sum(v[i] for i in r)
          nodesSelected = set(r)
          if all(all(x in nodesSelected for x in ancestors[y]) for y in r):
              maxSumValues = max(maxSumValues, sumValues)
      return maxSumValues
  </code></pre>
  <p>However, this becomes prohibitively expensive if K is large (e.g. N = 1,000,000, K = 500,000). Is there a polynomial algorithm in N that works for any K? Alternatively, can it be proven that the problem is NP-hard?</p>