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]
http://www.daixie0.com/contents/3/1239.html
本团队核心人员组成主要包括硅谷工程师、BAT一线工程师，国内Top5硕士、博士生，精通德英语！我们主要业务范围是代做编程大作业、课程设计等等。
我们的方向领域：window编程 数值算法 AI人工智能 金融统计 计量分析 大数据 网络编程 WEB编程 通讯编程 游戏编程多媒体linux 外挂编程 程序API图像处理 嵌入式/单片机 数据库编程 控制台 进程与线程 网络安全 汇编语言 硬件编程 软件设计 工程标准规等。其中代写代做编程语言或工具包括但不限于以下范围:
C/C++/C#代写
Java代写
IT代写
Python代写
辅导编程作业
Matlab代写
Haskell代写
Processing代写
Linux环境搭建
Rust代写
Data Structure Assginment 数据结构代写
MIPS代写
Machine Learning 作业 代写
Oracle/SQL/PostgreSQL/Pig 数据库代写/代做/辅导
Web开发、网站开发、网站作业
ASP.NET网站开发
Finance Insurace Statistics统计、回归、迭代
Prolog代写
Computer Computational method代做
因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
微信：codinghelp