Algorithm for the allocation of work with dynamic programming_问答_开发者

The problem is this:

Need to perform n jobs, each characterized by a gain {v1, v2,. . . , vn}, a time required for its implementation {t1, t2,. . . , tn} and a deadline for its implementation {d1, d2,. . . , dn} with d1<=d2<=.....<=d3. Knowing that the gain occurs only if the work is done by that time and that you have a single machine. Must describe an algorithm that computes the maximum gain that is possible to obtain.

I had thought of a recurrence equation with two parameters, one indicating the i-th job and the other shows the moment in which we are implementing : OPT(i,d) , If d+t_i <= d then adds the gain t_i. (then a variant of multiway choice ..that is min for 1<=i<=n).

My main prob开发者_如何转开发lem is: how can I find jobs that previously were carried out? I use a data structure of support?

As you would have written the equation of recurrence?

thanks you!!!!

My main problem is: how can I find jobs that previously were carried out? I use a data structure of support?
The trick is, you don't need to know what jobs are completed already. Because you can execute them in the order of increasing deadline.

Let's say, some optimal solution (yielding maximum profit) requirers you to complete job A (deadline 10) and then job B (deadline 3). But in this case you can safely swap A and B. They both will still be completed in time and new arrangement will yield the same total profit.
End of proof.

As you would have written the equation of recurrence?
You already have general idea, but you don't need a loop (min for 1<=i<=n).

max_profit(current_job, start_time)
    // skip this job
    result1 = max_profit(current_job + 1, start_time)

    // start doing this job now
    finish_time = start_time + T[current_job]
    if finish_time <= D[current_job]
        // only if we can finish it before deadline
        result2 = max_profit(current_job + 1, finish_time) + V[current_job];
    end

    return max(result1, result2);
end

Converting it to DP should be trivial.

If you don't want O(n*max_deadline) complexity (e.g., when d and t values are big), you can resort to recursion with memoization and store results in a hash-table instead of two-dimensional array.

edit
If all jobs must be performed, but not all will be paid for, the problem stays the same. Just push jobs you don't have time for (jobs you can't finish before deadline) to the end. That's all.

First of all I would pick the items with the biggest yield. Meaning the jobs that have the biggest rate in value/time that can match their deadline (if now+t1 exceeds d1 then it is bogus). Afterwards I check the time between now+job_time and each deadline obtaining a "chace to finish" of each job. The jobs that will come first will be the jobs with biggest yield and lowest chance to finish. The idea is to squeeze the most valuable jobs. CASES:

If a job with a yield of 5 needs 10 seconds to finish and it's deadline comes in 600 seconds and a job with the same yield needs 20 seconds to finish and it's deadline comes in 22 seconds, then I run the second one.

If a job with a yield of 10 needs 10 seconds to finish and it's deadline comes in 100 seconds while another job has a yield of 5 needs 10 seconds to finish and it's deadline comes in 100 seconds,I'll run the first one.

If their yield is identical and they take same time to finish while their deadline comes in 100 seconds,respectively 101 seconds, I'll run the first one as it wins more time.

.. so on and so forth..

Recursion in this case refers only to reordering the jobs by these parameters by "Yield" and "Chance to finish".

Remember to always increase "now" (+job_time)after inserting a job in the order. Hope it answers.

I read the upper comments and understood that you are not looking for efficiency you are looking for completion, so that takes the yield out of the way and leaves us with just ordering by deadline. It's the classic problem done by Divide et Impera Quicksort http://en.wikipedia.org/wiki/Quicksort