- C 1 (60.73 KiB) Viewed 35 times
- C 2 (74.36 KiB) Viewed 35 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!)