Dynamic Programming Distribution Algorithm

Question

The problem is this:

It is necessary to complete n tasks, each of which is characterized by a gain {v1, v2,. ,, vn}, the time required for its implementation {t1, t2,. ,, tn} and the deadline for its implementation {d1, d2 ,. ,, dn} with d1 <= d2 <= ..... <= d3. Knowing that winning only happens if work is being done by then and that you have one machine. Must describe an algorithm that calculates the maximum gain that can be obtained.

I was thinking of a recurrence equation with two parameters, one of which indicates the i-th task, and the other shows the moment at which we realize: OPT (i, d), If d + t_i <= d, then the gain t_i is added. (then the option in multipoints), which is minimal for 1 <= i <= n).

My main problem: how can I find tasks that were previously performed? Am I using a support data structure?

How would you write a recurrence equation?

thank you!!!!

Answer 1

My main problem: how can I find tasks that were previously performed? Am I using a support data structure?
The trick is that you do not need to know which tasks have already been completed. Because you can execute them in ascending order of time.

Say some kind of optimal solution (giving maximum profit) requires you to complete task A (deadline 10 ), and then task B (deadline 3 ). But in this case, you can safely replace A and B Both of them will still be completed on time, and the new arrangement will yield the same total profit.
The end of the proof.

How would you write a recurrence equation?
You already have a 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 do not need O(n*max_deadline) (for example, when the values ​​of d and t are large), you can resort to recursion with memoization and save the results in a hash table instead of a two-dimensional array.

change
If all tasks must be completed, but not all will be paid, the problem remains the same. Just click on assignments for which you do not have time (assignments that you cannot complete before the deadline) to the end. It's all.

Answer 2

First of all, I would choose the items with the highest yield. The value of jobs that have the largest indicator in cost / time, which can correspond to their deadline (if now + t1 exceeds d1, then this is fictitious). Subsequently, I check the time between now + job_time and each deadline, getting a "sequence to complete" each job. The jobs that come in first place will be the jobs with the highest profitability and minimal chances to finish. The idea is to squeeze the most valuable tasks. CASES:

If the task with harvest 5 takes up to 10 seconds, and it expires in 600 seconds, and the task with the same yield should be 20 seconds and the end in 22 seconds, then I start the second.

If a task with a crop of 10 takes 10 seconds and the end expires after 100 seconds and the other task has 5 needs 10 seconds and the end expires after 100 seconds, I started the first one.

If their profitability is identical, and they take the same time to finish, until their deadline expires after 100 seconds, respectively 101 seconds, I will start the first, since it wins more time.

.. so on and so forth

The recursion in this case refers only to the reordering of tasks according to these parameters using the "Exit" and "Chance to the end".

Remember to always increment "now" (+ job_time) after entering the job in order. I hope he answers.

Answer 3

I read the top comments and realized that you are not looking for the efficiency you are looking for to complete, so that you receive income and leave us with the order on time. This is a classic issue, Divide et Impera Quicksort http://en.wikipedia.org/wiki/Quicksort