Data Structures, Algorithms, & Applications in C++
Chapter 19, Exercise 17

  1. First examine the tasks making decisions on those for which Ti,1 = Ti,2. For these tasks, we choose way 1 when Ci,1 <= Ci,2 and way 2 when Ci,1 > Ci,2 because there can be no advantage to doing these tasks using the higher cost way.
  2. If we have tasks for which Ti,1 < Ti,2 and Ci,1 <= Ci,2, then we opt to do these tasks the first way because the first way takes less time and does not cost any more than the second way.
  3. If we have tasks for which Ti,1 > Ti,2 and Ci,1 >= Ci,2, then we opt to do these tasks the second way because the second way takes less time and does not cost any more than the first way.
  4. Renumber the remaining tasks 1, 2, ... m. Relabel the ways to perform each of these remaining tasks so that Ti,1 < Ti,2 and Ci,1 > Ci,2. For these remaining tasks, we obtain the following dynamic programming equations:

    c(m,j) = infinity, j < Tm,1
    c(m,j) = Cm,1, Tm,1 <= j < Tm,2
    c(m,j) = Cm,2, otherwise


    and

    c(i,j) = infinity, j < Ti,1
    c(i,j) = Ci,1 + c(i+1, j-Ti,1), Ti,1 <= j < Ti,2
    c(i,j) = min{Ci,1 + c(i+1, j-Ti,1), Ci,2 + c(i+1, j-Ti,2)}, otherwise

    for 1 <= i < m


We may determine the least cost way to perform the project as follows:
Step 1
Make decisions on tasks that fall into categories 1, 2, and 3. This takes O(n) time.
Step 2
Relabel the remaining m tasks and the ways to perform each task as described in item 4 above. This relabeling takes O(m) time.
Step 3
Compute the time, t', allowed for the remaining tasks by subtracting from t the time taken by the n-m tasks for which decisions were made in Step 1.
Step 4
Compute c(m,j) for 0 <= j <= t' using the equation for c(m,j) obtained in item 4 above. This takes O(t') time.
Step 5
Compute c(i,j) for i = m-1, m-2, ... 1, in that order, using the equation for c(i,j) developed in item 4 above. For each i, compute c(i,j) for 0 <= j <= t' (this can be done in any order). It takes O(mt') time to compute all of these c(i,j) values.
Step 6
c(1,t') gives the least cost needed to complete the remaining m tasks. The way each should be done is determined by using a traceback procedure for c(1,t'). Assume that c(1,t') != infinity. Therefore, it is possible to complete the remaining tasks taking no more than t' time.

The traceback for c(i,j) is recursive. When i = m, there are two cases to consider. If c(m,j) = Cm,1, do task m in way 1, otherwise do this task in way 2.

When i < m, there are also two cases to consider. If c(i,j) = Ci,1 + c(i+1, j-Ti,1), then task i is done in way 1 and we do a traceback for c(i+1, j-Ti,1) to determine the remaining decisions. Otherwise, task i is done in way 2 and we do a traceback for c(i+1, j-Ti,2) to determine the remaining decisions. The traceback takes O(m) time.


From the above description and analysis, we see that the overall complexity is O(nt).