# Python代写 | FIT2004 S2/2020: Assignment 2 – Dynamic

FIT2004 S2/2020: Assignment 2 – Dynamic
Programming

1 Robot in a corridor (12 marks)
Consider the following scenario: There is a corridor which is n floor-tiles long. Your robot starts
on the first tile. Each tile has an item on it, with some value (this value can be negative). The
robot will walk along the corridor, and at each tile, it can either pick up the item on that tile,
or not. Once the robot moves off the last tile, the scenario ends.
We wish to maximize the total value of items the robot picks up, but there is a problem. Picking
up items takes energy. The robot charges up energy when it is not picking up items, but it
loses energy when it picks up an item. It can always move forward (moving does not consume
energy) but sometimes it may be unable to pick up the current item.
The robot starts with 0 energy (i.e. it can never pick up the first item). It has 2 actions it can
perform:
• Pick up the item on the current floor tile, move to the next tile, and lose 1 energy. This
action can only be performed when the robot has at least 1 energy
• Move to the next floor tile and gain 1 energy
To solve this problem, you will write a function optimise_single_pickup(corridor).
1.1 Input
corridor is a list of integers representing the values of the items on each tile of the corridor.
This list will always contain at least 1 item. The i
th element of corridor corresponds to the
value on the i
th tile of the corridor. The first item’s value is therefore corridor. The robot
starts on tile 0.
1.2 Output
optimise_single_pickup returns a tuple with two elements. The first element is the maximum total value that the robot can obtain.
The second item is a list representing the choices the robot should make to obtain this value.
The values in this list are the integers 1 and 0. 0 means that the robot moved on without
picking up the item. 1 means that the robot picked the item on that tile and moved on. The
i
th item in this list corresponds to the action the robot takes on the i
th tile of the corridor.
1.3 Example
>>> optimise_single_pickup([4, 0, 4, 1, -3, 4, 3, 2])
(13, [0,0,1,0,0,1,1,1])
1.4 Complexity
optimise_single_pickup should run in O(N2
) time and space, where N is the length of
corridor

2 Robot in a corridor II (4 marks)
We have the same situation as Task 1, but now the robot is broken. When you instruct the
robot to pick up an item, it gets stuck in a loop and continues picking up items until its energy
reaches 0 (or until it reaches the end of the corridor). After that, it continues as normal.
The new actions the robot can take are as follows:
• If the robot has more than e ≥ 1 energy, pick up every item on the next e tiles, ending
on the tile after the last item that it picked up. In other words, it executes a series of e
“pick up” actions, without a chance for you to give further instructions. At the end of
this sequence of pick up actions, it will have 0 energy. Of course, if the end of the corridor
is reached before e tiles have been traversed, then the scenario ends.
• Move to the next floor tile and gain 1 energy
To solve this problem you will write a function optimise_multiple_pickup(corridor).
The input and output format are identical to Task 1. Note that you still record each pickup,
even if it is forced.
2.1 Example
>>> optimise_multiple_pickup([4, 0, 4, 1, -3, 4, 3, 2])
(11, [0,0,1,1,0,1,0,1])
>>> optimise_multiple_pickup([0,0,5,-4,1,1])
(2, [0,0,0,0,1,1])
In the second example, the robot still has 2 energy after it steps off the last tile. The amount
of energy is has left is not relevant.
2.2 Complexity
optimise_multiple_pickup should run in O(N2
) time and space, where N is the length of
corridor

3 Colour chooser (10 marks)
Consider the following problem: A paint warehouse is designing an interface to allow users to
choose a shade of a colour. The user will have already chosen the colour they are interested
in. They are then presented with a particular shade of that colour, and they can either accept
that shade (in which case they are done), or they can request a lighter or darker option (if a
valid option exists). If no valid lighter or darker option exists, they must choose the current
shade. We will refer to this process as a decision tree.
The shade which is presented to the user always respects their prior choices, i.e. if they said
The paint warehouse has data on which shades are more or less popular, and they want to
make the experience user friendly, so they need you to design a decision tree for the shades
which will minimise the expected number of choices each user has to make.
Specifically, each shade has a probability which is a number between 0 and 1 (inclusive) which
represents the proportion of users who have chosen that shade in the past. Each shade will
also be at some choice_depth, which is the number of decisions the user needs to make in
order to choose that shade. For the root of the decision tree, this is 1, since you at least need
to choose it. For each other shade, it is the number of shades that the user sees before getting
Let S be a set of shades. The cost of a particular decision tree for S is given by
X
s∈S
choice_depth(s) ∗ probability(s)
We want to find the minimum cost decision tree for some given set of shades S. To solve this
3.1 Input
shades is a list of numbers between 0 and 1 inclusive, representing the darkness/lightness of
each shade in S. Darker shades have lower values. This list will be sorted in ascending order.
probs is a list of numbers between 0 and 1 inclusive, representing the probabilities of each
3.2 Output
The output is a single number, the cost of the optimal decision tree. You do not need to return
any information about the structure of the decision tree.

3.3 Example
shades = [0.1, 0.2, 0.3, 0.4, 0.5]
probs = [0.25, 0.2, 0.05, 0.2, 0.3]
>>> 2.1
To help you understand the example, a visualisation of the optimal decision tree is provided,
along with an example of a different decision tree using the same information, which is not
optimal.
The root is the first choice, and the children of a node are the options presented to the user
when they select lighter/darker (since lower numbers are darker, the darker option is on the
left, and the lighter is on the right).
In the diagram below, the optimal decision tree for the example is shown. Each node represents a shade, where the first value is the lightness/darkness of the shade, and the second is its
probability.
Figure 1: The optimal decision tree.
(0.2, 0.2)
(0.1, 0.25) (0.5, 0.3)
(0.4, 0.2)
(0.3, 0.05)
Figure 2: A suboptimal decision tree
(0.2, 0.2)
(0.1, 0.25) (0.4, 0.2)
(0.3, 0.05) (0.5, 0.3)
The cost of the decision tree in Figure 1 is given by 1∗0.2+2∗(0.25+0.3)+3∗0.2+4∗0.05 = 2.1.
The cost of the decision tree in Figure 2 is given by 1∗0.2+2∗(0.25+0.2)+3∗(0.05+0.3) = 2.15
Note that since this question deals with floating point values, it is possible for rounding errors
to be introduced by your algorithm. You will not be penalised for computer rounding errors. E-mail: [email protected]  微信:itcsdx 