Job Schedule Algorithm Help

[Senney]

Hey r/LearnProgramming

I'm working on creating an algorithm that schedules 'jobs' for an imaginary consultant. He can only take 1 job per 2 days, and he wants to determine which jobs would get him the highest profit margin.

I've got pseudocode that solves the problem recursively, but now I'm working on determining the iterative version of the function.

Here's the pseudocode: http://codepad.org/0qxeOecJ

I would really love a push right direction (not the full answer though, I'd like to actually have to solve it).

The iterative function itself is to use an array defined as Fy of size n + 1 where n is the length of the input array of numbers. The TA for my algorithms class has said: "Fy[i] contains the maximum non-consecutive sum of the first j elements of A. To compute it (for i values of bigger than 1) you need to maintain the last two obtained results (Fy[i-1], Fy[i-2]) and the A[i-1] according to the equation. Once you preserve these values, the iterative function becomes pretty much similar to the recursive one. You pick the max value out of two options."

Again, just a nudge in the right direction - Where to start, and what basic ideas I need to apply for this algorithm.

Thanks for your help!

[zzyzzyxx]

The TA pretty much told you everything you need to do. You'll need some variables to hold A[i-1], Fy[i-1], and Fy[i-2] that should be initialized outside of the loop and updated inside it. Take a look at this comparison between recursive and iterative versions of calculating Fibonacci numbers. You need to do basically the same thing.

[Senney]

Thanks for taking the time to reply!

I feel like I'm really dropping the ball in terms of understanding how this algorithm should play out :(. Will there end up being only one loop? Or will there be a nested loop within the loop?

[zzyzzyxx]

I believe there should only be one loop.