# 动态编程代写 | FIT2004 S2/2021: Assignment 2 – Dynamic Programming

本次澳洲作业案例分享是动态**编程代写**的一个assignment

## Learning Outcomes

This assignment achieves the Learning Outcomes of:

1) Analyse general problem solving strategies and algorithmic paradigms, and apply them

to solving new problems;

2) Prove correctness of programs, analyse their space and time complexities;

4) Develop and implement algorithms to solve computational problems.

In addition, you will develop the following employability skills:

Text comprehension

Designing test cases

Ability to follow speciﬁcations precisely

**Planning**

1. Read the assignment speciﬁcation as soon as possible and write out a list of questions

you have about it.

2. Clarify these questions. You can go to a consultation, talk to your tutor, discuss the tasks

with friends or ask in the forums.

3. As soon as possible, start thinking about the problems in the assignment.

It is strongly recommended that you do not write code until you have a solid feeling

for how the problem works and how you will solve it.

4. Writing down small examples and solving them by hand is an excellent tool for coming

to a better understanding of the problem.

As you are doing this, you will also get a feel for the kinds of edge cases your code

will have to deal with.

5. Write down a high level description of the algorithm you will use.

6. Determine the complexity of your algorithm idea, ensuring it meets the requirements.

**Implementing**

1. Think of test cases that you can use to check if your algorithm works.

Use the edge cases you found during the previous phase to inspire your test cases.

It is also a good idea to generate large random test cases.

Sharing test cases is allowed, as it is not helping solve the assignment.

2. Code up your algorithm, (remember decomposition and comments) and test it on the

tests you have thought of.

3. Try to break your code. Think of what kinds of inputs you could be presented with which

your code might not be able to handle.

Large inputs

Small inputs

Inputs with strange properties

What if everything is the same?

What if everything is diﬀerent?

etc…

**Before submission**

Make sure that the input/output format of your code matches the speciﬁcation.

Make sure your ﬁlenames match the speciﬁcation.

Make sure your functions are named correctly and take the correct inputs.

Make sure you zip your ﬁles correctly (if required)

## Documentation (3 marks)

For this assignment (and all assignments in this unit) you are required to document and com-

ment your code appropriately. This documentation/commenting must consist of (but is not

limited to)

For each function, high level description of that function. This should be a one or two

sentence explanation of what this function does. One good way of presenting this infor-

mation is by specifying what the input to the function is, and what output the function

produces (if appropriate)

For each function, the Big-O complexity of that function, in terms of the input. Make

sure you specify what the variables involved in your complexity refer to. Remember that

the complexity of a function includes the complexity of any function calls it makes.

Within functions, comments where appropriate. Generally speaking, you would comment

complicated lines of code (which you should try to minimise) or a large block of code

which performs a clear and distinct task (often blocks like this are good candidates to be

their own functions!).

### Game Master (9 marks)

You and your friends are playing a table-top role playing game, and you are the game master.

You want to design an encounter, and you have a certain diﬃculty target that you want to

reach. You also have a list of monsters, and you want to select a group of monsters whose

diﬃculty ratings sum up to the target diﬃculty.

You are interested in ﬁnding out how many diﬀerent possible encounters there are which satisfy

this requirement. To solve this problem, you will write a function

count_encounters(target_difficulty, monster_list).

**1.1 Input**

target_difficulty is a non-negative integer.

monster_list is a list of tuples. Each tuple represents a type of monster. The ﬁrst value in

each tuple is a string, which is the name of the type of monster. The second value is a positive

integer, representing the diﬃculty of that particular type of monster.

**1.2 Output**

count_encounters returns an integer, which is the number of diﬀerent sets of monsters whose

diﬃculties sum to target_difficulty. A type of monster may be used more than once in an

encounter.

**1.3 Example**

target_difficulty = 15

monster_list = [(“bear”, 5), (“imp”, 2), (“kobold”, 3), (“dragon”, 10)]

print(count_encounters(target_difficulty, monster_list))

>>> 9

In the above example, the possible encounters are:

1 dragon, 1 bear

1 dragon, 1 kobold, 1 imp

3 bear

2 bear, 1 kobold, 1 imp

1 bear, 2 kobold, 2 imp

1 bear, 5 imp

5 kobold

3 kobold, 3 imp

1 kobold, 6 imp

Your answer does not need to compute these possible sets of monsters, this list is provided to

help you understand the example answer of 9

**1.4 Complexity**

count_encounters should run in O(DM) where

D is the value of target_difficulty

M is the length of monster_list