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...
-
Sandra Kapple asks Maria VanHusen about using futures contracts to protect the value of the Star Hospital Pension Plans bond portfolio if interest rates rise. VanHusen states: a. Selling a bond...
-
The frame is subjected to the load of 5 k. Determine the vertical displacement at C. Assume that the members are pin connected at A, C, and E, and fixed connected at the knee joints B and D. EI is...
-
Research whether there are any ethics opinions in your state that concern the use of social media. Are there any court cases?
-
For the doll-manufacturing enterprise described in Problem 7, Andy Mendoza has determined that $10,000 worth of advertising will increase sales volume by 400 dolls. Should he spend the extra amount...
-
Employment Law Wedow v. City of Kansas City, Missouri Female firefighters were not given proper firefighting uniforms (while male firefighters were given two uniforms), which put them at risk for...
-
Use a dot plot to display the data. The data represent the systolic blood pressures (in millimeters of mercury) of 30 patients at a doctor's office. Organize the data using the indicated type of...
-
wwwwwwwwww wwwwww Consider a pure endowment, 2-period, 2- country world where all housholds have logarithimc utility placing equal weight on both periods. The endowments for the two countries are...
-
A company sells a fire pit for $400 per unit and has $45,000 in fixed costs. The variable cost per unit is $325. What is the net income (loss) if the company sells 542 units?
-
TranscribedText: Intel is currently trading at $34.69, interest rates are currently 5.3%, and 1.5 year call options on Intel with a strike of $37 are trading at an implied vol of 41%. Suppose you...
-
Wallace Company sold equipment originally costing $650,000 for $320,000 cash. The accumulated depreciation as of the date of the sale was $300,000. What would be the journal entry for this...
-
Dozier Company produced and sold 1,000 units during its first month of operations. It reported the following costs and expenses for the month: Direct materials Direct labor $ 83,000 $ 42,000 Variable...
-
Figure the Total Cost (TC) for these 2 input/output combinations. Write your answer down somewhere, you'll need your total cost values to figure the next column. Input (Labor) Output TFC TVC TC MC...
-
If saving per worker initially exceeds investment per worker, how is the steady state capital- labor ratio achieved? Illustrating a graph to explain your answer.
-
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....
-
The post-closing trial balance for Cortez Co. is as follows. The subsidiary ledgers contain the following information: (1) accounts receivable J. Anders \($2,500,\) E Cone \($7,500,\) T. Dudley...
-
Presented below are the purchases and cash oe journals for Reyes Co. for its first month of operations. In addition, the following transactions have not been journalized for July. The cost of all...
-
Presented below are the sales and cash receipts journals for Wyrick Co. for its first month of operations. In addition, the following transactions have not been journalized for February 2008....
Study smarter with the SolutionInn App