Algorithm for the allocation of work with dynamic programming -

the problem this:

need perform n jobs, each characterized gain {v1, v2,. . . , vn}, time required implementation {t1, t2,. . . , tn} , deadline implementation {d1, d2,. . . , dn} d1<=d2<=.....<=d3. knowing gain occurs if work done time , have single machine. must describe algorithm computes maximum gain possible obtain.

i had thought of recurrence equation 2 parameters, 1 indicating i-th job , other shows moment in implementing : opt(i,d) , if d+t_i <= d adds gain t_i. (then variant of multiway choice ..that min 1<=i<=n).

my main problem is: how can find jobs carried out? use data structure of support?

as have written equation of recurrence?

thanks you!!!!

my main problem is: how can find jobs carried out? use data structure of support?
trick is, don't need know jobs completed already. because can execute them in order of increasing deadline.

let's say, optimal solution (yielding maximum profit) requirers complete job a (deadline 10) , job b (deadline 3). in case can safely swap a , b. both still completed in time , new arrangement yield same total profit.
end of proof.

as have written equation of recurrence?
have general idea, don't need loop (min 1<=i<=n).

max_profit(current_job, start_time)     // skip job     result1 = max_profit(current_job + 1, start_time)      // start doing job     finish_time = start_time + t[current_job]     if finish_time <= d[current_job]         // if can finish before deadline         result2 = max_profit(current_job + 1, finish_time) + v[current_job];     end      return max(result1, result2); end 

converting dp should trivial.

if don't want o(n*max_deadline) complexity (e.g., when d , t values big), can resort recursion memoization , store results in hash-table instead of two-dimensional array.

edit
if jobs must performed, not paid for, problem stays same. push jobs don't have time (jobs can't finish before deadline) end. that's all.