Geek Answers Handbook

Algorithm mashing and backtracking

Currently, I am participating in several interviews and came across several algorithmic issues that completely surpassed me. I was wondering if any of you could help explain the strategy for solving this problem of the example or perhaps provide some kind of pseudo code.

Thanks a bunch!

Problem: You are a freelance contractor, and your jobs change once a week. Works are divided into two groups: ls and hs. If you choose a task with hs, you have to prepare a week in advance, not paying attention to the work. Ls works do not require such preparation.

Determine the optimal work plan, taking into account two arrays l and h of size n, where n is the number of weeks.

So, from my understanding, given the table below:

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

The best way would be NHNHL for a reward of 650. But I do not understand how to do this in a compact efficient algorithm.

+6
source share
3 answers

Each week, you either choose a high voltage job or a low voltage job. If you choose to work with low voltage at week n, then the optimal solution is the optimal solution for the previous (n-1) weeks. If you choose high voltage operation, then the optimal solution is the optimal solution for the previous (n-2) weeks. This gives a repetition 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 wins for work with low voltage and high voltage at week n, respectively. If you store F_L, F_H and F in arrays and increment them in ascending n order, this is dynamic programming and gives an O (n) time algorithm for finding the optimal solution up to week n. Obviously, for F (n), you need to save whether you chose to work with high voltage or low load for week n to restore the optimal sequence of tasks.

+4
source

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

I think the easiest way to model these problems is to use what I call forwarding, which is a kind of dynamic programming. You start at the beginning of the node, and then find the maximum possible value and path for the nodes adjacent to the starting node. Then calculate the same for the nodes next to them, etc., until you get the maximum for all possible end nodes. This shows the main 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 simply stores the maximum value possible in each cell. So at the end, you should examine the values ​​in the last column of aiMaximumSum, and the highest value will be the response value. This code does not save the path. To do this, you will need to have a second array and store a path for each cell (regardless of whether the maximum value was obtained from the string L or H).

+1
source

Implement it as user2566092:

 def f(n): return max(fl(n),fh(n)) def fl(n): if n>=0: return f(n-1)+x["low"][n] else: return 0 def fh(n): if n>=0: return f(n-2)+x["high"][n] else: return 0 x={"low":(30,5,20,25,500),"high":(0,50,70,100,110)} print f(4) #650

EDIT: if you want it in O (n):

 x={"low":(30,5,20,25,500),"high":(0,50,70,100,110)} flist=[] fhlist=[] fllist=[] for i in range(5): if i-1>0: fllist.append(flist[i-1]+x["low"][i]) else: fllist.append(x["low"][i]) if i-2>=0: fhlist.append(flist[i-2]+x["high"][i]) else: fhlist.append(x["high"][i]) flist.append(max(fhlist[i],fllist[i])) print fllist print fhlist print flist #[30, 5, 70, 125, 650] #[0, 50, 100, 150, 210] #[30, 50, 100, 150, 650]
0
source

More articles:


All Articles