C++
Posted: Sun May 15, 2022 10:17 am
C++
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 3$ 6$ = $25 skip Take Take $7 skip Take $9 $9 3$ = $23 skip Take $9 Take Take $6 $7 Take 1 LA
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!)
- C 1 (60.73 KiB) Viewed 37 times
- C 2 (74.36 KiB) Viewed 37 times
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!)