Dynamic Programming

Problem 4 (bonus): 1. Assume you have three type of coins, S1, $2, and $5, and a wallet that fits up to 5 coins. Use Dynamic Programming to find the smallest value (in whole dollars) that cannot be created and fit into the wallet. Here are a few examples how values can be created: you can create S7 by putting in 1 coin of S5, and 1 coin of $2. you can create $18 by putting in 3 coins of S5, 1 coin of S2, and 1 coin of $1 2. Consider the generalization of the problem above: you have m type of coins, a wallet where you can fit at most k coins, and want to know the smallest value (in whole dollars) that cannot fit into the wallet. Write a program that takes as input a file containing the following sequence of numbers: the sequence of the m different types of coins and solves the problem above implementing the algorithm you developed in part 1. Test it on the file "coins.dat" (submit the code of the algorithm and the solution it outputs)