Geek asks and answers

Maximum Value Planning Algorithm

I have a list of projects, and each project requires you exactly two days , which must be completed, and has a set date. let P [i] .id, P [i] .duedate and p [i] .value - the project identifier, the project completion date and the value that you get if you complete the project on time (on time or before the due date)

write an algorithm that takes A as an input array and returns a graph of what projects you will do and when to maximize the value that you get. the output of the algorithm is an array B such that B [i] is the identifier of the project on which you will work during day i, i> = 1.

no more than one project for a certain date, and you will not receive the cost of the project if you have not completed it by the set date, today is day 0, and you will start working on projects from the first day (completion date is an integer), for example, if the completion date the project is 5, you can work on it on days 3 and 5)

1- write an algorithm. 2- prove that the algorithm is optimal? 3- what is the time complexity of the algorithm?

+3
source share
1 answer

If all values ​​are the same, just, just a greedy approach, choosing the smallest possible date, works well.

When the values ​​are different, you can use a similar approach, but this time through dynamic programming (I will assume that your timeline is discrete).

Max{due date} V, , , V V[i], DP:

V [0] = 0, V [1] = max {value_x 1, V [i] = Max {V [i-2] + value_x i, V [i-1]}

value_x i , , i. V [i-2], V [ i].

, , , , .

+1

More articles:


All Articles