Requirements Implement the following two functions: • unsigned max_coins (vector coins) This function receives a vector of coins and returns the maximum profit Mario can gain. vector coin_indices (vector 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!)
Requirements Implement the following two functions: • unsigned max_coins (vector coins) This function receives a vector of coins and returns the maximum profit Mario can gain. vector coin_indices (vector 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!)
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
100%
Do in c++
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
O O
3$
6$
= $25
skip Take
$9
skip Take
$9
Take
$7
3$
= $23
skip Take
$9
Take
$6
Take
Take
$7
$1
%24
![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!)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa718a826-d64e-400e-b12c-c58dd8741b19%2F82e52b66-673a-4ff2-b5ef-d3aedf73c269%2Fczw1i6z_processed.jpeg&w=3840&q=75)
Transcribed Image Text: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 Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 1 images
Follow-up Questions
Read through expert solutions to related follow-up questions below.
Follow-up Question
how can i fix this
ed website asks me for a return
and my doctor told us we should return result
please can you fix ?
![$44799
C+mario.cpp
positions [i]=positions [i+1];
}
49
50
else
51
52
{
53
54
positions[i]=positions [i+2];
55
56
positions[i].push_back(i);
57
58
}
59
60
}
61
62
reverse (positions [0].begin(), positions[0].end());
return result;
63
64
65
66}
67
home/mario.cpp 63:5 Spaces: 4 (Auto)
All changes saved
Console Terminal
▶ Run
✓ Mark
In file included from main.cpp:1:
mario.cpp: In function 'std::vector<unsigned int> coin_indices (std::vector<unsigned int>)':
mario.cpp:63:13: error: 'result' was not declared in this scope
63 |
return result;
Ammmmm
I
X Program exited with code 1
45
46
48
G+ main.cpp
ì](https://content.bartleby.com/qna-images/question/76cc9931-7b0a-49fd-9b58-1730b911c637/1b518276-2238-44a3-8c8d-5558a5ed9502/cegso0t_processed.png)
Transcribed Image Text:$44799
C+mario.cpp
positions [i]=positions [i+1];
}
49
50
else
51
52
{
53
54
positions[i]=positions [i+2];
55
56
positions[i].push_back(i);
57
58
}
59
60
}
61
62
reverse (positions [0].begin(), positions[0].end());
return result;
63
64
65
66}
67
home/mario.cpp 63:5 Spaces: 4 (Auto)
All changes saved
Console Terminal
▶ Run
✓ Mark
In file included from main.cpp:1:
mario.cpp: In function 'std::vector<unsigned int> coin_indices (std::vector<unsigned int>)':
mario.cpp:63:13: error: 'result' was not declared in this scope
63 |
return result;
Ammmmm
I
X Program exited with code 1
45
46
48
G+ main.cpp
ì
Solution
by Bartleby ExpertKnowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education