dynamic programming代做、代写c/c++，Java编程语言、代做algorithm留学生

日期：2019-02-19 10:51

4 Homework 3

Deliverables. You should solve the problems in this homework using dynamic programming.

Recall that a dynamic programming solution MUST include

1. A definition of subproblems

2. A recursion, including a base case

3. A bound on the number of subproblems (as in: the number of subproblems is O(n

2k))

4. A bound on the recursion time (as in: the recursion takes time O(n))

Unless explicitly stated otherwise, pseudocode and examples are not required.

Problem 4.1. (Difficulty 3) There are n gold coins placed at positions {1, . . . , n} on a line.

The gold coin at position i has a positive weight wi

. You can pick any of the n coins, except

that if you pick the gold coin at position i then you cannot pick the adjacent ones, that is,

the ones at positions i 1 and i + 1. Design a dynamic programming algorithm to compute

the maximum total weight of the coins you can collect. Also explain how to compute

the sequence of coins to be taken. Make your algorithm as fast as you can.

For example, if n = 3 and the gold coins have weights w1 = 20, w2 = 30, w3 = 15, then

the maximum total weight is 20 + 15 = 35 and is obtained by picking the coins at positions

1 and 3.

Problem 4.2. (Difficulty 3) Bob has to plan his working life for the next T years. There

are m jobs that Bob can do, and every year Bob must do exactly one job. Each job pays

different amounts depending on the year. (For example, being a mail carrier will pay less

and less with time, while being a computer scientist will pay more and more with time.)

Specifically, during a year t a job j pays W(j, t). Bob is currently doing job 1 and can switch

job at most S times.

Give an algorithm to compute the maximum possible earning of Bob for the next T years.

The running time of the algorithms should be polynomial in T, m, and S.

Problem 4.3. (Difficulty 3) [Taken from Jeff Erickson’s book] Vankin’s Mile is an American

solitaire game played on an n × n square grid. The player starts by placing a token on any

square of the grid. Then on each turn, the player moves the token either one square to the

right or one square down. The game ends when player moves the token off the edge of the

board. Each square of the grid has a numerical value, which could be positive, negative,

or zero. The player starts with a score of zero; whenever the token lands on a square, the

player adds its value to his score. The object of the game is to score as many points as

possible.For example, given the grid below, the player can score 8 ?6 + 7?3 + 4 = 10 points

by placing the initial token on the 8 in the second row, and then moving down, down, right,

down, down. (This is not the best possible score for this grid of numbers.)

1. Describe and analyze an efficient algorithm to compute the maximum possible score

for a game of Vankin’s Mile, given the n × n array of values as input.

22

2. In the European version of this game, appropriately called Vankin’s Kilometer, the

player can move the token either one square down, one square right, or one square left

in each turn. However, to prevent infinite scores, the token cannot land on the same

square more than once. Describe and analyze an efficient algorithm to compute the

maximum possible score for a game of Vankin’s Kilometer, given the n × n array of

values as input.