留学生Python编程辅导、辅导Python编程Christmas tree

All submitted work must be done individually without consulting someone elses solutions in accordance

with the Universitys Academic Dishonesty and Plagiarism policies.

IMPORTANT! Questions 1a–b and 2a–c should be submitted via Blackboard as pdf (no handwriting!).

The implementation required for Questions 2d should be done in Ed, and submitted

via Ed.

Questions

Christmas is coming up and you have decided to invest in a Christmas tree production company.

The company has k different forests growing Christmas trees, let us call these F = {forest 1,

forest 2, . . . , forest k}. Your task is to plan an optimal cutting tree schedule for the next Y years.

To be able to sell a Christmas tree it has to be a mature tree. You estimate that each forest i,

will mature wi,j Christmas trees in year j. Christmas trees have a limited lifetime: a tree which

matures in year j can only be cut down and sold in that year, or in the δj − 1 years afterwards.

After that the tree will be too old to sell and will fall down naturally.

The economic predictions also show that if the company harvests more than uj Christmas trees

in year j, the market would be flooded and the Christmas tree market would crash...you don’t

want that to happen.

Additionally, cutting too many trees from a single forest destabilises the local ecosystem. Since

you are environmentally conscious, you cannot harvest more than τi trees total from forest i over

the entire Y years.

Your task is to develop an algorithm that determines a Christmas tree harvesting schedule

that maximizes the number of Christmas trees sold (you should only return the number of trees

that should be sold).

To aid you in your task you have been provided with an implementation of the Ford-Fulkerson

algorithm. You may assume without proof that this algorithm correctly returns the maximum

flow of a given flow network G in O(m2

log C) time using O(n + m) space, where C is maximum

flow in G.

1. [20 points] Consider the case when Y = 3, k = 2, δ1 = δ2 = 2 and δ3 = 1.

(a) Formulate the problem of determining a schedule with maximum number of Christmas

trees sold as a network flow problem. [10 points]

(b) Argue why your algorithm is correct. [10 points]

2. [80 points] In this question your task is to generalise your solution to k forests, Y years

and variable tree lifespans.

(a) Formulate the problem of determining a schedule with maximum profit (maximum number

of Christmas trees sold) as a network flow problem for a given Y , k and δ1, . . . , δY .

[15 points]

(b) Argue why your formulation is correct. [15 points]

(c) Prove an upper bound on the time complexity of your algorithm. [20 points]

(d) Implement your algorithm (in Ed) and test it on the provided instances.

Each instance is using the following format:

1

kYδ1...δYτ1...τkw1,1...w1,Yw2,1...wk,Yu1...uY

You may assume that all the values given are non-negative integers. The output should

be the maximum number of Christmas trees that can be sold.

[30 points]