2023年11月25日

算法代写 | CSC 373 Dynamic Programming

本次算法代写Dynamic Programming主要是解决三个模拟的动态规划案例，要求给出求解步骤和伪代码。

Required filename for MarkUs submission: a2.pdf

Due: before 6:00pm on Fri. 8 Feb.

Remember to write the full name and MarkUs username of every group member (up to three) prominently on your submission.

Please read and understand the policy on Collaboration given on the Course Information Sheet. Then, to protect yourself, list on the front of your submission every source of information you used to complete this homework (other than your own lecture and tutorial notes). For example, indicate clearly the name of every student from another group with whom you had discussions, the title and sections of every textbook you consulted (including the course textbook), the source of every web document you used (including documents from the course webpage), etc.

For each question, please write up detailed answers carefully. Make sure that you use notation and terminology correctly, and that you explain and justify what you are doing. Marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

For every problem, give a Dynamic Programming solution, following the steps outlined in class. Don’t forget to justify that your recurrence relation is correct based on the recursive structure of the problem, and to analyze the time complexity of your final algorithm.

1. Riding a bicycle in Toronto

Suppose the streets in some section of Toronto are modelled as a simple grid, and you want to travel from the lower-left corner (coordinate (0,0)) to the upper-right corner (coordinate (m,n)). Further, to simplify the problem, suppose that every street is one-way so you can only travel right or up (never left and never down).

But riding a bicycle in Toronto is dangerous! So every street segment has a probability that riding on that segment will result in an accident. Let p i,j be the probability that riding right from coordinate (i − 1,j) to (i,j) results in an accident, and q i,j be the probability that riding up from coordinate (i,j − 1) to (i,j) results in an accident. As usual, all probabilities are real numbers in the interval [0,1]. The probability that you have no accident on a path is simply the product of the probabilities that you have no accident on each street segment of the path.

Your goal is to find a path from (0,0) to (m,n) with the maximum probability of having no accident.

2. Study group lunch

Suppose you want to buy B burgers, C fries, and D drinks at your favourite fast-food place, for a study group you’re organizing (this question is most certainly not about good eating habits)! The unit price of each item is p b (for burgers), p c (for fries), and p d (for drinks). You also own n coupons N 1 ,…,N n . Each coupon N i is a combo that offers you b i burgers, c i fries, and d i drinks at price p i . Each coupon can only be used at most once. Note: All values are natural numbers, which means some of them could be equal to zero (e.g., it’s possible for a coupon to offer a deal that includes only drinks and fries, but no burger; it’s also possible for a coupon to offer more burgers, or fries, or drinks than you need).

What is the minimum amount of money you need to pay to get at least B burgers, C fries, and D drinks? It’s okay if you end up with more food (or drinks) than you need.

3. Homework planning

You have n assignments A 1 ,…,A n where A i = (p i ,t i ), p i ∈ Z + is the number of points earned if you complete the assignment, and t i ∈ R + is the time required to complete the assignment. You also have a total time T ∈ R + available to complete all the assignments.

Find a subset of assignments that you can complete within your time limit and that maximizes the total number of points obtained. (Note: you cannot use arbitrary real numbers as array indices.)