Overview Super Mario is on the run collecting coins. In level # 1, whenever he takes...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Overview Super Mario is on the run collecting coins. In level # 1, whenever he takes a coin, the next coin is automatically blocked with an iron brick. Which coins should Mario take in order to maximize his gains? $3 $9 $2 $7 $3 $6 $9 $1 0 0 0 3$ skip Take $9 3$ skip Take $9 Take $7 Take $7 6$ skip Take $9 Take $6 Take $1 = $25 = $23 Requirements Implement the following two functions: unsigned max_coins (vector<unsigned> coins) This function receives a vector of coins and returns the maximum profit Mario can gain. vector<unsigned> coin_indices (vector<unsigned> coins) This function receives a vector of coins and returns the indices of the coins Mario should take to get the maximum profit. For example, function coin_indices must return [1, 3, 6] for the example provided above. Note. You should not assume that function coin_indices is called after function max_coins. These two functions must be implemented independently. To avoid duplicating code, you can define a third function that is called from within both functions. Hints This assignment, is on dynamic programming. Therefore, start by thinking of a solution that mimics one of the dynamic programming examples covered in class: • Describe the optimal solution using the optimal solution of smaller sub-problems. • Think of how you will store the solutions of the sub-problems in order to avoid computing them more than once. Write a bottom-up solution. A top-down solution (using memoization) might crash with a stack overflow error (the depth of the recursion is limited by how much memory there is because each recursive call reserves a record on the memory stack!) Overview Super Mario is on the run collecting coins. In level # 1, whenever he takes a coin, the next coin is automatically blocked with an iron brick. Which coins should Mario take in order to maximize his gains? $3 $9 $2 $7 $3 $6 $9 $1 0 0 0 3$ skip Take $9 3$ skip Take $9 Take $7 Take $7 6$ skip Take $9 Take $6 Take $1 = $25 = $23 Requirements Implement the following two functions: unsigned max_coins (vector<unsigned> coins) This function receives a vector of coins and returns the maximum profit Mario can gain. vector<unsigned> coin_indices (vector<unsigned> coins) This function receives a vector of coins and returns the indices of the coins Mario should take to get the maximum profit. For example, function coin_indices must return [1, 3, 6] for the example provided above. Note. You should not assume that function coin_indices is called after function max_coins. These two functions must be implemented independently. To avoid duplicating code, you can define a third function that is called from within both functions. Hints This assignment, is on dynamic programming. Therefore, start by thinking of a solution that mimics one of the dynamic programming examples covered in class: • Describe the optimal solution using the optimal solution of smaller sub-problems. • Think of how you will store the solutions of the sub-problems in order to avoid computing them more than once. Write a bottom-up solution. A top-down solution (using memoization) might crash with a stack overflow error (the depth of the recursion is limited by how much memory there is because each recursive call reserves a record on the memory stack!)
Expert Answer:
Related Book For
Business Law The Ethical Global and E-Commerce Environment
ISBN: 978-0071317658
15th edition
Authors: Jane Mallor, James Barnes, Thomas Bowers, Arlen Langvardt
Posted Date:
Students also viewed these programming questions
-
C plc wants to reward its directors for their service to the company and has designed a bonus package with two different elements as follows. The directors are informed of the scheme and granted any...
-
C and D agree to form a partnership. C is to contribute $50,000 in assets and to devote one-half time to the partnership. D is to contribute $20,000 and to devote full time to the partnership. How...
-
C Co. reported a retained earnings balance of $370,000 on December 31, 2017. In September 2018, C determined that insurance premiums of $54,000 for the three-year period beginning January 1, 2017,...
-
Single PlantwideandMultiple Production Department Factory Overhead Rate Methodsand Product Cost Distortion The management of Nova Industries Inc. manufactures gasoline and diesel engines through two...
-
Why should organizations take employees' personal needs into account in providing benefits such as time off from work?
-
Maxime S.A. is a small company that processes wild mushrooms found in the forests of central France. For many years, Maximes products have had strong sales in France. However, companies from other...
-
Based on the information in the Botox Application, what would happen to the optimum price and quantity if the government had collected a specific tax of \(\$ 75\) per vial of Botox? What welfare...
-
The comparative statements of Corbin Company are presented below and on page 884. Additional data: The common stock recently sold at $19.50 per share. Instructions Compute the following ratios for...
-
cananyone help with this and check if its correct Diaz Company owns a machine that cost \( \$ 125,600 \) and has accumulated depreciation of \( \$ 92,900 \). Prepare the entry to record the disposal...
-
Show that if G is a CFG in Chomsky normal form, then for any string w L(G) of length n 1, exactly 2n 1 steps are required for any derivation of w.
-
Aging of receivables; estimating allowance for doubtful accounts Instructions Chart of Accounts Starting Question Aging of Receivables Schedule Instructions Additional Question Trophy Fish Company...
-
A publisher finds that the mean number of grammatical errors per page of a book is six. Find the probability that the number of grammatical errors found on any given page is (a) exactly four, (b) at...
-
Define monetary base. How does the monetary base differ from the money supply?
-
A river barge, whose cross section is approximately rectangular, carries a load of grain. The barge is \(28 \mathrm{ft}\) wide and \(90 \mathrm{ft}\) long. When unloaded, its draft (depth of...
-
Can the approaches discussed in this chapter be used in emerging economies? What adjustments, if any, would you recommend?
-
How many real positive values of \(r\) satisfy the following. (a) \(\frac{d R}{d r}(r, 0.05)=0\) (b) \(\frac{d R}{d r}(r, 0.4)=0\) (c) \(\frac{d R}{d r}(r, 0.8)=0\)
-
The Vineland-II is used with individuals with intellectual disabilities to measure __________________ emotional intelligence adaptive functioning maladaptive behavior intellectual ability
-
During 2012, Cheng Book Store paid $483,000 for land and built a store in Georgetown. Prior to construction, the city of Georgetown charged Cheng $1,300 for a building permit, which Cheng paid. Cheng...
-
Williams was 18 years old when she was admitted to Baptist Health Systems for treatment of serious health conditions. The age of majority for contracting in Williams's state was 19. Williams was...
-
Approximately four years before his death, Dr. Martin Luther King, Jr., gave Boston University possession of some of his correspondence, manuscripts, and other papers. He did this pursuant to a...
-
Brian Petty was both a police officer in Nashville, Tennessee, and an officer in the Army Reserve. In October, he informed the department that he would be deployed to Iraq at the end of the year....
-
You are evaluating two investments that each require $1,000. One is a municipal bond that pays 9 percent interest annually. The interest is exempt from federal and state taxes. The other is a...
-
You should buy insurance and establish an emergency fund before you invest, and you should invest early. Write About It Write several paragraphs explaining why you should take these steps before...
-
List four specific sources of financial information.
Study smarter with the SolutionInn App