dyanmic programming table

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

1) This is a homework question
2) This isn't strictly related to perl (Although it will be implimented using perl :) )

Question:
I have to devise a dynamic-programming solution (a table) for the fastest time to process all ofthe jobs in a queue, using 2 computers. ther are N jobs, For the I'th job it takes Ai time in Machine_A and Bi time in machine_B, where Bi != Ai.

Example:
Job:  Time in A    Time in B
1         10           5
2          8           10
3          1           2
4          6           7

Total Time needed is 12.
Send job:   To Machine
1               A
2               B
3               B
4               A
[download]

The concpet is simple, i'm just having trouble formulating what needs to be int he table, and how to get it there.

Thanks in advance guys ... I've been workign on this all weekend and gotten no where with the table ... can't think of anyone else that might be able to help.

Comment on dyanmic programming table Download Code

Replies are listed 'Best First'.
RE: dyanmic programming table by little (Curate) on Nov 05, 2000 at 20:39 UTC
As this is your homework I'm not going to give you clear advice nor a ready to use solution. seems you are about missing the job as you have chosen all longer times, so rethink that think about in which order you wannt to compare which values which way do you know how to assign times and machines, so it would be easier to you to get the machine to use while knowing it's time spent on a job? when you know about all the above you could very quick sort lists (or even hash values) when using the Schwartzian Tranform Have a nice day All decision is left to your taste	[reply]
RE (tilly) 1: dyanmic programming table by tilly (Archbishop) on Nov 05, 2000 at 23:21 UTC
I likewise won't post an actual answer. However conceptually you need to separate out figuring out what goes where from displaying it. The best solution for the first part is probably going to be to walk through all possible allocations of jobs to machines and then pick the best one. (I suggest recursion.) FWIW I have not thought hard about this, but I don't know of a sub-exponential solution. I can improve the base, but not the fact of it being exponential.	[reply]