subject

After running the teleportation delivery company Algo Express for many years, you discover the power of dynamic programming. You leave the company to start a new venture (DPAlgo Express) that can process very big delivery orders. In particular, each order now takes several days for the teleportation machine to complete. Suppose on a certain day, n customers give you packages to deliver. Each delivery i should be made within di days, takes ti days to deliver, and the customer pays you pi dollars for doing it on time (if you don't do it on time you get paid 0 dollars). On-time delivery means that if package i is due within di-k days, the delivery should be completed on or before day k to be on time (that is, it should start on or before day k -ti1). As before, your teleportation machine can only make one delivery at a time. Input: A set of n deliveries with due dates di E N, di payments Pi > 0 for each delivery i 61,-.. , n} 1, number of days needed for delivery ti EN, t 1 and Example to iron out the semantics of the input-Suppose we have two deliveries with di = 1, t1 = 1 and d2 = 4, t2-3. Then we can schedule the first delivery on day 1, the delivery will take the entire day and finish on day 1 We can then schedule the second delivery on day 2, which will finish on day 4. In this case, both the deliveries are completed on the day of their deadline and thus we get their respective profits. Describe and analyze an efficient algorithm to determine which deliveries to make and in what order so as to maximize your profit. (Note: unlike the previous version of the problem, deliveries may now take more than one day). Your algorithm should have a pseudo-polynomial running time running time polynomial in n and T, where T is the latest deadline among all deliveries. Unfortunately your "greedy" competitor from homework 4, Algo Express, is catching up to your lead in the very big delivery business. You decide to focus on maximizing your market share to beat out the competition. To do this, you have decided to neglect profits and only maximize the number of deliveries that you make (remember - deliveries may still take more than 1 day each). Describe and analyze a polynomial time algorithm to determine which deliveries to make and in what order so as to maximize the number of deliveries you make. The input to the problem is the same as before, but this time your algorithm should run in time polynomial in n alone We recommend using dynamic programming for each of the above parts. Please provide a brief proof of correctness for your recursive equations.

ansver
Answers: 2

Other questions on the subject: Computers and Technology

image
Computers and Technology, 22.06.2019 13:00, Cookie320
Write a program which asks you to enter a name in the form of first middle initial last. so you might enter for example samuel p. clemens. use getline to read in the string because it contains spaces. also, apparently the shift key on your keyboard doesn’t work, because you enter it all lower case. pass the string to a function which uses .find to locate the letters which need to be upper case and use toupper to convert those characters to uppercase. the revised string should then be returned to main in the form last, first mi where it will be displayed.
Answers: 1
image
Computers and Technology, 22.06.2019 19:00, SoccerHalo
How is the number 110 written when expanded out to place values in the base 2 (binary) number system? options: 2 x 4 + 3 x 2 + 4 x 1 1 x 2 + 1 x 2 + 0 x 2 1 x 100 + 1 x 10 + 0 x 1 1 x 4 + 1 x 2 + 0 x 1
Answers: 1
image
Computers and Technology, 23.06.2019 06:10, erick7123
The head restraint should be adjusted so that it reaches a. the top of your ears b. the base of your skull c. the top of the head
Answers: 1
image
Computers and Technology, 23.06.2019 16:30, saintsfan2004
How to do this programming flowchart?
Answers: 3
You know the right answer?
After running the teleportation delivery company Algo Express for many years, you discover the power...

Questions in other subjects:

Konu
Health, 09.02.2021 16:40
Konu
Mathematics, 09.02.2021 16:40
Konu
Mathematics, 09.02.2021 16:40