Submit Link: https://classroom.github.com/a/I74gIvkM
Write a function to solve the following problem using dynamic programming:
Given a value \(N\), if we want to make change for \(N\) cents, and we have an infinite supply of each \(S=\left\{S 1, S 2, \ldots, S_{m}\right\}\) valued coins, how many ways can we make the change? The order of the coins does not matter. For example, if \(N=10\) and \(S=\{2,5,3,6\}\), there are five solutions.
Hint: All solutions can be divided into the set of solutions that contain at least one of the \(m\) th coin and those that do not.
Write a function to solve the following problem using dynamic programming:
Given a rod of length \(n\) inches and an array \(\boldsymbol{P}\) of prices that contains prices of all pieces of size \(s \leq n\), determine the maximum value obtainable by cutting up the rod in even inch increments and selling the pieces. For example, if rod is 8 inches and the piece length values are given by \(\boldsymbol{P}=\{1,5,8,9,10,17,17,20\}\), then the maximum obtainable value is 22 by cutting pieces of length 6 and 2.
Hint: Call the function \(V(n)\) the maximum value obtainable for a rod of length \(n\). Then
\[ V(n)=\max _{c \in\{0,1, \ldots n-1\}}\{\boldsymbol{P}[c]+V(n-c)\} \]
Write a function to solve the following problem using dynamic programming:
Given weights \(\boldsymbol{W}\) and values \(\boldsymbol{V}\) of \(n\) items, put these items in a knapsack of capacity \(C\) to get the maximum total value in the knapsack. As an example, if \(\boldsymbol{W}=\{10,20,30\}\) and \(\boldsymbol{V}=\{60,100,120\}\) and \(C=50\), then the maximum value is 220 , obtained by selecting the second and third item. Bonus: argue that this problem is a generalization of the problem in Question 2.
Hint: Possible subsets of items can be split up into including the \(n t h\) item or not including the \(n\)th item.
Write down an economic problem that interests you specifically and express it as a dynamic programming problem. Solve the problem on your computer and report things about the results that you find interesting - this could be plots of decision rules, simulated results of agents solving the problem, or whatever else comes to mind.