Step-by-step Guides to reach Dynamic Programming Solution
The following are step-by-step guides to finish this lab. Answer all questions in red in this document, and modify/extend the code as instructed. In the end, submit this document on Blackboard, and the coin_change.cpp on autograder.
Compile and run the starter code first, and understand the solutions given for UnlimitedCoinChange( ).
To investigate whether dynamic programming can be used to improve its performance, we check if it has two characteristics: overlapping optimal substructure and overlapping subproblems. (Ref: CLR textbook, see the RodCuttingExplained reading posted on the weekly schedule page).
* Optimal substructure refers to the fact that (optimal) solutions to a problem incorporate (optimal) solutions to related subproblems, which we may solve independently. Another way to put it is that the problem has a recursive solution.
Can you write a formula for the mv, which denotes the minimum number of coins required to make value v with the given set of coins? If v cannot be expressed with the set of coins, mv is infinite.
* Overlapping subproblem: Add cout statement to the function, to display a line such as the following whenever the function is called:
UnlimitedCoinChange (value=14) called
Compile and run your program, and note all instances where UnlimitedCoinChange is called to solve a problem multiple times (a.k.a., overlapping subproblems) below:
What are the overlapping subproblems you found?
2. To avoid recomputing overlapping subproblems, we will use a table to store subproblem solutions.
Analyze the UnlimitedCoinChange( ) function, as an algorithm, what are its input and output? Which input parameter(s) are not changed, and which input parameters are varying during the recursive calls?
int UnlimitedCoinChange (const vector & coins, int value)
b. Design the table to use following the guideline:
The table used by dynamic programming provides a lookup: given a subproblem’s input, it tells us the subproblem’s solution.
We typically use array or vector, where the index is the subproblem’s input, and the value of the array/vector element is the subproblem solution.
vector subProblemSolutions; //subProblemSolutions[i] tells us the minimum number of coins that we can make value=i with; if a certain value cannot be expressed with the coins, its entry should be set to INT_MAX
Draw the subProblemSolution table used for UnlimitedCoinChange(…, value=31,..) below. Show the size of the table, what’s stored in the table entry. Note that you don’t need to fill in the table’s entries, just illustrate using an example or two.
vector coins{3, 5, 6, 10};
3. Tabulation version:
Write a new function, unlimitedCoinChange_Tabulation() that solves the problem using the tabulation approach. The following is the pseudocode:
//Return the minimum number of coins we need to use to make the given @value, assuming there are unlimited supplies for each type of coins given by @coins.
int UnlimitedCoinChange_Tabulation (const vector & coins, int value)
{
//1. Declare the table (see step 2 above)
//2. Based upon the base cases from UnlimitedCoinChange, fill out the initial entries of the table
//3. Write a for loop to solve all problems, from smallest (1) to largest (value)
For (int cur_v=2; cur_v<=value; cur_v++)
{ // solve subproblem cur_v, and store the solution in the table
//Note: use the optimal substructure found in step 1
}
//4. Return solution stored in table for @value
}
4. Develop a Memoization approach following the instruction below
Write a wrapper function, in which we declare and initialize the table, and then call the recursive function
Int UnlimitedCoinChange_Wrapper (const & coins, int value)
{
//1. Declare and initialize all entries to -1, meaning all problems are not yet solved
//2. Call memoized recursive solution, and return what’s returned by the function
}
Extend UnlimitedCoinChange to the following memoized version:
int UnlimitedCoinChange_Memoized (const vector & coins, int value, vector & subProblemSolutions)
Note that to memoized a recursive function, do the following:
At the entry to the function, check the table to see the current problem has been solved before or not. If so, return the table entry; if not, proceed.
At the exit point of the function (i.e., before each return statement), stores the result in the table.
5. How are the optimal solutions achieved?
Now, consider how to extend dynamic programming solutions above so that we not only report a) The minimum number of coins required, but also b) the coins used to make a given value.
a). In pure recursive solution given, this is done by taking best subproblem solution and append to it the branch that leads to the subproblem (the i-th coin)
//General case of UnlimitedCoinChange
int curMin = INT_MAX; //we don't have a solution yet
//used to save “current subproblem solution”
vector curBest;
int curSol;
for (int i=0;i coins{3, 5, 6, 10};
1). Only draw two levels of the tree (root node, and its child nodes).
2). Label what’s returned by each child node (both the int value, and the value of curBest vector)
Note: you don’t need to trace each recursive call to the base case.
3). Follow logic of the above general case, to find out what’s returned by the root.
4). Mark which branch of the root node yields the best solution
b).(Extra Credit) In Dynamic Programming, we just store the current option (the branch in the decision tree) taken at each subproblem in a second table:
vector subProblemSolution; //as before
vector firstCoinUsed; //which branch (as in recursion solution) leads to optimal solution?
The second table provides a lookup: for a value to make it maps to the first coin to use (that leads to an optimal solution eventually) in the decision tree.
Based upon your work in step a) above, show the content of subProblemCoinUsed[31], I.e., what’s the first coin to use in the decision tree that leads to optimal solution?
c). (Extra Credit) Extend your memorized solution so that the subProblemCoinUsed table is used to store all “first coin” used.
int UnlimitedCoinChange_WrapperExtended (const & coins, int value)
{
//1. Declare and initialize both tables: all entries to -1, meaning all problems are not yet solved
//2. Call memoized recursive solution, and return what’s returned by the function
//3. Use the firstCoinUsed table to output all coins used
}
int UnlimitedCoinChange_MemoizedExtended (const vector & coins, int value, vector & subProblemSolutions, vector & firstCoinUsed)
