本次Python代写是完成一个机器人走动的程序

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[0]. 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

“darker” to shade X, then all subsequent shades will be darker than shade X.

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

to that shade, plus one.

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

problem, you will write a function optimal_shade_selector(shades, probs)

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

shade in S. probs[i] is the probability of the shade represented by shades[i].

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]

print(optimal_shade_selector(shades,probs))

>>> 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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected] **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。