Lesson 1

In the project selection problem, there is a set of projects, which we conveniently denote by \([n]\). Each project \(i\) has an associated profit \(p_{i}\). It can be either negative or positive. A positive profit means that completing the project yields a profit of \(p_{i}\). A negative profit means that you need to spend \(-p_{i}\) monetary units to complete the project.

For some project pairs \((i,j)\), there are constraints like “project \(i\) can be performed only if project \(j\) is also performed.” For example, to start software development, you first need to hire programmers and rent an office. To start drilling a well, you need to rent the necessary equipment. To earn profit from baking, you need to buy ingredients and rent a bakery space.

A subset \(A \subseteq [n]\) of projects is called feasible if it satisfies all given constraints: for any constraint \((i,j)\), if \(i \in A\), then \(j \in A\). The goal is to find a feasible subset of projects with maximum total profit: \[\operatorname{profit}(A)=\sum_{i \in A}p_{i} \ .\] In particular, the empty set is always feasible. Its total profit is zero.