a.) Suppose our bill denominations were 1, 4, 7, 13, 28, 52, 91, 365 and we have
ID: 3833154 • Letter: A
Question
a.) Suppose our bill denominations were 1, 4, 7, 13, 28, 52, 91, 365 and we have a greedy algorithm that repeatedly takes the largest bill value and adds it so long as it doesn't exceed our target value. name a target value that doesn't return the optimal set.
(b) Now we want to solve the problem of using the fewest number of bills to make k Dream Dollars. Let D[1..8] denote the size-8 array that holds the given denominations; so D[1] = 1, D[2] = 4, D[3] = 7, etc. For any k 0 , 0 k 0 k and j, 1 j 8, let C(k 0 , j) denote the fewest number of bills from denominations in D[1..j] that make change for k 0 Dream Dollars. Write down a recurrence for C(k 0 , j), for 0 k 0 k, 1 j 8. Make sure that the base cases are all carefully specified. Hint: The trivial observation is that in the optimal change for k 0 using denominations in D[1..j], we either use a bill with denomination D[j] or we don’t.
(c) The recurrence from (b) can be implemented as a recursive function, though you don’t need to do this. Now think about the memoized version of this recursive function using a 2-dimensional (k + 1) × 8 table in which the table-slot Table[k 0 , j] is filled with C(k 0 , j). Figure out the order in which this table in filled and then write pseudocode for a function that finds and returns the fewest number of bills needed to make change for k Dream Dollars, when the denominations come from D[1..8]. This function uses two nested loops to fill out the table.
(d) Write a function that takes as input k, D, and Table (filled out using the function in (c)) and returns the optimal set of bills of denominations D[1..8] used to make change for k.
Explanation / Answer
(a) Consider the target values of 455, If greedy is used then the denominations will be
455-365=90-52=38-28=10-7=3=1+1+1, so denomination will be 365, 52, 28, 7, 1 , 1, 1 total 7
where as there exists lesser number of denominations 91, 91, 91, 91, 91.
(b) Base cases:
C(k0,1) = k0
C(0, j) = 0 for all 1<= j <= 8
Recursive case:
if k0 < Dj then C(k0,j) = C(k0,j-1)
else It contains two cases Either we use one denomination of Dj or do not use any Dj denomination
C(k0,j) = min { C((k0, j-1) , 1+C(k0-Dj, j) }
(c) FillTable(D, k)
{
initialize C[][] to (k+1) by 8 matrix;
/// Lets say indces of matrix starts from 0
for j in 0.. 7 {
C[0][j] = 0; } //0 represents 0 target, and i is ith denomination
for i in 0 ..k {
C[i][0] = i; }
for i in 1 .. k {
for j in 1 .. 7 {
if (i < D[j] )
then C[i][j] = C[i][j-1];
else
C[i][j] = min(C[i][j-1] , 1+C[i-D[j]][j] );
end if
}}
}
At the end the optimum value is contained by C[k][7]
(d) denominations(D, C, k, j)
{
if (C[k][j] = C[k][j-1] )
then return denominations(D,C, k, j-1)
else
result = denominations(D, C ,k-D[j], j);
result = result.add(D[j]);
return result;
end if
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.