The River City redevelopment authority wants to add a minimum of one thousand new parking spaces in the downtown area. The following table shows the estimated cost (in millions of dollars) of the 4 proposed projects and the number of spaces each would yield (in hundreds).

Project 1 2 3 4 Cost 16 9 11 13 Spaces 8 3 6 6 The authority wants to meet its goal at minimum total cost. Assume that every project is available only on an all-or-nothing basis.

(a) Formulate a knapsack ILP to choose an optimal parking program.

(b) Solve your knapsack by inspection.