拍手笑清风 拍手笑清风
关注数: 30 粉丝数: 142 发帖数: 402 关注贴吧数: 2
用任意语言实现要求算法设计 难!! 1。 Negar and Young are managing the construction of restaurants along 55th Street. The n possible locations are along a straight line, and the distances of these locations from the start of 55th Street (at the Lake) are, in miles and in increasing order, m1, m2, …, mn. The constraints are as follows: • At each location, the TAs may open at most one restaurant. The profit from opening a restaurant at location i is pi dollars, where pi > 0 and i = 1, 2, …, n. • Any two restaurants should be at least k miles apart, where k is a positive integer. Give an efficient dynamic programming algorithm to compute the maximum total profit subject to the given constraints. Define the subpr 2. Consider a row of n coins of values v(1), …, v(n), where n is even. Two players take turns removing a coin from an end of the row until all coins have been removed. In each turn, a player selects either the first or the last coin from the row, removes it from the row permanantly, and receives the value of the coin; the coin must be taken either from the right end or the left end of the line so that the remaining coins remain contiguous. The goal for each player is to maximize the total value of the coins collected. Each player plays optimally. Example: If the coins are arranged in the order 10, 25, 10, 1 (with values 10, 25, 10, 1 cents), then Player 1 should pick the penny ( 1 cent) because picking the dime (10 cents) would permit Player 2 to pick the quarter (25 cents). If Player 1 picks the penny first, then out of 10, 25, 10, no matter what Player 2 picks, the quarter will go to Player 1. So if each player plays optimally, Player 1 will collect 26 cents, while Player 2 collects 20 cents. Give a dynamic programming algorithm to compute an optimal strategy for the first player. Define the subproblems to be solved. For full credit, define all variables introduced. State the recurrence that solves all the subproblems in terms of smaller subproblems. Include the solution to the base cases (i.e., smallest subproblems). (5 points) Write pseudocode for yo ur algorithm. Explain how your algorithm works and why it is correct. Analyze the running time of your algorithm.
1 下一页