Algorithm Memoization and Backtracking

Question

I am currently studying for a few job interviews and came across a few algorithm questions that completely stumped me. I was wondering if any of you could help explain the strategy for solving this example problem or possibly provide any pseudocode.

Thanks a bunch!

Problem: You are a freelance contractor and your available jobs change weekly. The jobs are split into two groups, ls and hs. If you choose a job from hs, you must prepare the week beforehand by taking no job. Ls jobs require no such preparation.

Determine your optimal plan of working, given two arrays l and h of size n where n is the amount of weeks.

So from my understanding, given a table below:

╔═══╦══╦════╦════╦════╦═════╦═════╗
║   ║  ║ 0  ║ 1  ║ 2  ║  3  ║  4  ║
╠═══╬══╬════╬════╬════╬═════╬═════╣
║ l ║  ║ 30 ║  5 ║ 20 ║  25 ║ 500 ║
║ h ║  ║  0 ║ 50 ║ 70 ║ 100 ║ 110 ║
╚═══╩══╩════╩════╩════╩═════╩═════╝

The optimal path would be NHNHL for a reward of 650. But I am stumped on how to do this in a compact efficient algorithm.

Answer 1

Each week you either choose a high stress job or a low stress job. If you choose a low stress job at week n, then the optimal solution is the optimal solution for the previous (n-1) weeks. If you choose a high stress job, then the optimal solution is the optimal solution for the previous (n-2) weeks. This gives a recurrence for dynamic programming:

F(n) = max(F_L(n), F_H(n))

F_L(n) = F(n-1) + x_L(n)

F_H(n) = F(n-2) + x_H(n)

where x_L(n),x_H(n) are the payoffs for the low stress and high stress jobs at week n respectively. If you store F_L,F_H and F in arrays and build up in increasing order of n, this is dynamic programming and gives an O(n) time algorithm to find the optimal solution up to week n. Obviously for F(n) you need to store whether you chose a high stress or low stress job for week n in order to recover the optimal sequence of jobs.

Answer 2

Another way to look at this is to model the data as a graph. If you model the weights as edges, you can then find the maximum path in the graph using the Djikstra algorithm.

I think the easiest way to model these problems is to use what I call forward aggregation, which is a kind of dynamic programming. You start at the beginning node and then find the maximum possible value and path for the nodes adjoining the starting node. Then calculate the same for the nodes next to those and so on, until you have a maximum for all the possible ending nodes. This shows the essential code:

int xColumn = 1;
while( true ){
    if( xColumn > iNumberOfColumns ) break;

    // first do low stress row
    int xRow = 1; // low stress
    int iCurrentCellValue = aiValues[xColumn][xRow];
    if( xColumn == 1 ){
        aiMaximumSum[1][1] = iCurrentCellValue;
    } else {
        if( aiMaximumSum[xColumn - 1][1] > aiMaximumSum[xColumn][2] ){
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][1];
        } else {
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][2];
        }
    }

    // next do high stress row
    int xRow = 2; // low stress
    int iCurrentCellValue = aiValues[xColumn][xRow];
    if( xColumn == 1 || xColumn == 2 ){
        aiMaximumSum[1][1] = iCurrentCellValue;
    } else {
        if( aiMaximumSum[xColumn - 2][1] > aiMaximumSum[xColumn - 2][2] ){
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][1];
        } else {
            aiMaximumSum[xColumn][xRow] = iCurrentCellValue + aiMinimumSum[xColumn - 1][2];
        }
    }

    xColumn++;
}

This code just stores the maximum value possible in each cell. So at the end you would examine the values in the final column of aiMaximumSum and the highest value would be answer value. This code does not store the path. To do that you would have to have a second array and for each cell store the path (whether the max value came from the L or H row).