# Python代写算法 | COMP 3027/3927 Assignment 2

Algorithms 3027/3927

This assignment is for both COMP3027 and COMP3927 students.

Task 1: Social Distancing [30 marks]

You and your genius friend earned enough licensing fees from the deep quantum neural networks to retire. Finally, you can indulge in your lifelong dream of running a fleet of Mexican food buses called Nacho Bus-iness. You want to set them up along a street in downtown for Cinco de Mayo. However, due to social distancing requirements, the buses cannot be placed too close together. Your goal is to find a placement of the buses satisfying the social distancing requirement that maximizes total revenue.

Formally, you are given as input an array R of n positive integers (not necessarily distinct) and the social distancing requirement d ≥ 0. The integer R[i] is the amount of revenue earned by a food bus placed at location i on the street. You can place as many buses as you wish, subject to the social distancing requirement: if a bus is placed at location i, then the nearest location that we can place another bus is i−d and i+d; no other bus can be placed at locations i−d+1,…,i+d−1. Your goal is to design an efficient dynamic programming algorithm to determine the maximum revenue that can be earned by a placement of food buses that satisfy the social distancing requirement. (Note that we are only interested in the revenue, not the actual placement.)

For example, consider the input R = [3027, 3927, 2123, 2823, 3530, 5045] and d = 3. The optimal solution is to place buses at locations 1 and 5 for a total revenue of 3927 + 5045 = 8972. For the same R and d = 2, the optimal solution is to place buses at locations 1, 3 and 5 for a total revenue of 3927 + 2823 + 5045 = 11795. (Arrays start with index 0.)

3027
Figure 1: Optimal solution for d = 2

3027
Figure 2: Optimal solution for d = 3

What we expect to see: Definition of OPT(…), and its parameters

What we expect to see: a recurrence that relates each subproblem to “smaller” subproblems. We just want to see a clear description of the recurrence here. The justification for the recurrence goes into (e).

What we expect to see: A description of the base cases and the values that OPT(..) takes on these base cases.

using the optimal values of the subproblems.

What we expect to see: The sufficiency of the base cases, i.e. the recurrence will always end up at a base case, the correctness of the recurrence and the values for the base cases, and that you correctly obtained the optimal revenue from OPT(..).

(f) Prove the time and space complexity of your algorithm.

What we expect to see: An analysis of the running time and space required to compute all the OPT(..) values and to obtain the maximum revenue from OPT(..)

Task 2: Grid Climbing [70 marks]

Congratulations! You’ve made it to the finals of the World Grid Climbing competition. You start at the bottom-left corner of an n × m grid and are only allowed to climb rightwards or upwards. Each grid position (i, j) has a score S[i, j]. (The bottom-left position is (0, 0) and the top-right is (n − 1, m − 1).) You have an energy budget of B. Moving right costs cr amount of energy and moving up costs cu. The numbers B, cr and cu are non-negative integers. A climbing path consists of a sequence of rightwards and upwards moves and is feasible if the total energy cost is at most the budget. The goal is to find the maximum total score that can be obtained by a feasible climbing path. (Note that we are only interested in the score, not the actual path.)

For instance, suppose S is the following grid, B = 10, cu = 3, and cr = 1. Then, the optimal path is (0,0) → (0,1) ↑ (1,1) → (1,2) → (1,3) ↑ (2,3) for a total score of 5+4+100+7+9+10 = 135 and cost of 2 × cu + 4 × cr = 10.

2145 8 3 9 10 3 100 7 3 5468

Figure 3: The grid S

2145 8 3 9 10 3 100 7 3 5468

Figure 4: The optimal path

For COMP3027: your algorithm should take O(nmB) time and space for full marks. For COMP3927: your algorithm should take O(nm) time and space for full marks; an O(nmB) time and space algorithm is worth 50 marks.

What we expect to see: Definition of OPT(…), and its parameters

What we expect to see: a recurrence that relates each subproblem to “smaller” subproblems. We just want to see a clear description of the recurrence here. The justification for the recurrence goes into (e).

What we expect to see: A description of the base cases and the values that OPT(..) takes on these base cases.

using the optimal values of the subproblems.

What we expect to see: The sufficiency of the base cases, i.e. the recurrence will always end up at a base case, the correctness of the recurrence and the values for the base cases, and that you correctly obtained the optimal score from OPT(..).

What we expect to see: An analysis of the running time and space required to compute all the OPT(..) values and to obtain the optimal score from OPT(..).

Submission details

Exemplar for Knapsack

(a) Define the subproblems needed by your algorithm.

Consider the items in some arbitrary order. Define OPT(i,w) to be the optimal solution to the knapsack problem consisting of the first i items and weight limit w for 0 ≤ i ≤ n and 0 ≤ w ≤ W. When i = 0, this corresponds to a knapsack problem with no items.

OPT(i, w) =

􏰄OPT(i−1,w)
max{vi + OPT(i − 1, w − wi), OPT(i − 1, w)}

ifwi >w, otherwise

Thebasecasesarewheni=0. Inthiscase,OPT(0,w)=0forall0≤w≤W.

The most value achieved is in the subproblem OPT(n, W ).

to the original problem from OPT(..).

The base cases are sufficient as each OPT(i, w) depends on some OPT(i−1, w). Thus, the recurrence will always end up at OPT(0, w) for some w. We have OPT(0, w) = 0 since the most value that can be achieved with no items is 0.

We now prove the correctness of the recurrence. Let S(i,w) be the optimal solution for the first i items with weight limit w. The recurrence for OPT(i, w) is correct because:

• if wi > w, then S(i,w) cannot contain item i and so is a subset of the first i − 1 items with weight at most w, so S(i, w) = S(i − 1, w) and OPT(i, w) = OPT(i − 1, w)

• ifwi ≤w,theneitheritemiisinS(i,w)ornot:

Finally, the optimal value for the original problem is OPT(n,W) as by definition of OPT, this is the most value that can be achieved by a subset of all n items with a weight limit of W.

(f) Prove the time and space complexity of your algorithm.