Question

Construct the visualization matrix for the following coin problem and find its optimal solution:

Coins: Penny, Nickle, Dime, and Quarter The amount= 27cents

USE DYNAMIC PROGRAMMING METHOD

Dynamic Programming

Let c[k,x] be the minimum number of coins for the amount x using the first k coins.

         Goal: find a recurrence relation for c[k, x].

       There are only two possible choices:

           1. amount x includes the largest coin which is dk

                 c[k, x] = 1 + c[k, x – dk]

          2. amount x does not include the largest coin

c[k, x] = c[k - 1, x ]

       Among these two choices, we always pick the smallest one.

Goal: find a recurrence relation for c[k, x]

c[k, x] = MIN (1 + c[k, x – dk], c[k - 1, x ])

c[k, x] = c[k - 1, x ], if x < dk

c[k, 0] = 0

c[1, x] = x

where 1 ≤ k ≤ n and 0 ≤ x ≤ m.

Solution to the problem is c[n, m]

Example of Money Changing Problem   d1 =1    d2=4 d3=6    and the amount = 8

	0	1	2	3	4	5	6	7	8
k==1 1 cent	0	1	2	3	4	5	6	7	8
k=2 4 cents	0	1	2	3	1	2	3	4	2
k=3 6 cents	0	1	2	3	1	2	3	1	2

c[k, x] = MIN (1 + c[k, x – dk], c[k - 1, x ])

c[k, x] = c[k - 1, x ], if x < dk

c[k, 0] = 0

c[1, x] = x

where 1 ≤ k ≤ n and 0 ≤ x ≤ m                The minimum number of coins= C[3,8]=2

Answer 1

We have

1 penny = 1 cent

1 nickel = 5 cents

1 dime = 10 cents

1 quarter = 25 cents

We will use dynamic programming to solve this problem

  

Transitions of dp are as follows :

As we have two choices either to pick last coin or don't pick it.

Here is Visualization matrix for

coins = {  Penny, Nickle, Dime, and Quarte } = { 1, 5 ,10, 25 }

We have converted each currency to cent using below formulas

1 penny = 1 cent

1 nickel = 5 cents

1 dime = 10 cents

1 quarter = 25 cents

Amount = 27 cents

Below is visulization matrix :

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
k=1	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27
k=2	0	1	2	3	4	1	2	3	4	5	2	3	4	5	6	3	4	5	6	7	4	5	6	7	8	5	6	7
k=3	0	1	2	3	4	1	2	3	4	5	1	2	3	4	5	2	3	4	5	6	2	3	4	5	6	3	4	5
k=4	0	1	2	3	4	1	2	3	4	5	1	2	3	4	5	2	3	4	5	6	2	3	4	5	6	1	2	3

Min no of coins to make 27 = 3

as 27 = 25 + 1 +1

Below Is code for reference

#include<bits/stdc++.h>
using namespace std;
void coin_change( int coins[], int total_coins, int Amount )
{
    int Max = Amount + 1;
    int dp[total_coins + 1][Amount + 1];
    for (int i = 0; i <= Amount; i++) dp[0][i] = INT_MAX - 1;
    for (int i = 1; i <= total_coins; i++) dp[i][0] = 0;

    for (int i = 1; i < total_coins + 1; i++)
        for (int j = 1; j < Amount + 1; j++)
            if (coins[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = min(1 + dp[i][j - coins[i - 1]], dp[i - 1][j]);

    cout << "       ";
    for (int i = 0; i <= Amount; i++)  cout << i << " "; cout << "\n";

    for (int i = 1; i <= total_coins; i++)  {
        cout << "K = " << i << "| ";
        for (int j = 0; j <= Amount; j++)
            cout << dp[i][j] << " ";
        cout << "\n";
    }
    cout << "\nMin coins = " << dp[total_coins][Amount] << "\n"; 

}
int main()
{   int total_coins, Amount;
    cin >> total_coins >> Amount;
    int coins[total_coins];
    for (int i = 0; i < total_coins; i++) cin >> coins[i];
    coin_change(coins, total_coins, Amount);
    return 0;
}

Below is screenshot of code along with output