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, 23.06.2019 00:30, vane3152
If joey was single and his taxable income was $9,500, how much would he pay in taxes each year?
Answers: 1
image
Computers and Technology, 23.06.2019 03:50, nakeytrag
Iam a bacterium. i cause stomach cramps and diarrhea. i am caused by eating rotten foodssuch as chicken, fish, or eggs. sometimes turtles carry my bacteria. what am i?
Answers: 2
image
Computers and Technology, 23.06.2019 06:00, tchloe448
What makes myhexadecimalnumber a child of mynumber? which methods does myhexadecimalnumber inherit directly from the mynumber class? what can an instance of the mynumber class do? what can an instance of the myhexadecimalnumber class do? which methods are overridden? why are they overridden? how many examples of overloading are there? why was this done? where is the super keyword used? what is it doing? why isn’t the incoming value set immediately in the second myhexadecimalnumber constructor? how many examples can you find of an inherited method being called?
Answers: 1
image
Computers and Technology, 23.06.2019 17:00, evanwall91
What does the faves button do? a. users mark a web page as a favorite b. leads other readers to favor a specific page c. readers sort and align their favicons, or favorite icons d. leads users to a message board where they can post questions
Answers: 1
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
Mathematics, 26.09.2019 22:20