Consider the coin denomination array (CD) and the sum of the coin values (S) assigned to you. Use the dynamic programmin
Posted: Sat Nov 27, 2021 10:41 am
Consider the coin denomination array (CD) and the sum of the
coin values (S) assigned to you. Use the dynamic programming
algorithm discussed in class to determine the minimum number of
coins and the actual coin values that one would pick up so that the
sum of the coin values is S. Show the contents of the MNC and LCP
arrays for each iteration, as discussed in the slides. Discuss how
you would trace the solution to determine the actual coin values
that need to be picked up for the given S.
Assume an infinite supply of coins for each value. Break any tie
in favor of the coin with a lower index in the CD array.
*Please don't write a code*
Coin Denomination (CD) Array
4 5
8
9
Sum of the Coin Values (S)
20
coin values (S) assigned to you. Use the dynamic programming
algorithm discussed in class to determine the minimum number of
coins and the actual coin values that one would pick up so that the
sum of the coin values is S. Show the contents of the MNC and LCP
arrays for each iteration, as discussed in the slides. Discuss how
you would trace the solution to determine the actual coin values
that need to be picked up for the given S.
Assume an infinite supply of coins for each value. Break any tie
in favor of the coin with a lower index in the CD array.
*Please don't write a code*
Coin Denomination (CD) Array
4 5
8
9
Sum of the Coin Values (S)
20