Algerithms. Create an angerithm for the following, not a full working program. A

Question

Algerithms. Create an angerithm for the following, not a full working program.

Apply the dynamic programming algorithm to find all the solutions to the change-making problem for the denominations 1, 2, 5 and the amount n = 11.

Below is just an example for a simular question using generic inputs. The algerithm should look simular to the following lines of code.

Algorithm OptimalCoins(D[1..m], C[1..m, 0..n], i, j)
//Finds the coins composing an optimal change
//Input: Arrays D[1..m] of coin denominations, table C[1..m, 0..n]
//generated by the dynamic programming algorithm for amount n,
// integers i (1 i m) and j (1 j n)
//Output: List L[1..i] of coins composing an optimal solution to
//the change problem for the first i denominations and amount j
for k 1 to i do L[k] 0
if C[i, j] <
while i > 0 and j > 0 do
if C[i, j] = C[i 1, j]
i i 1
else
L[i] L[i] + 1 //add one coin of denomination D[i]
j j D[i]
return L

Explanation / Answer

for k 1 to i do L[k] 0
if C[i, j] <
while i > 0 and j > 0 do
if C[i, j] = C[i 1, j]
i i 1
else
L[i] L[i] + 1 //add one coin of denomination D[i]
j j D[i]
return L

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.