Coin Change :Dynamic Programming

Question

The code I have written solves the basic coin change problem using dynamic programming and gives the minimum number of coins required to make the change. But I want to store the count of each coin playing part in the minimum number.

What I am trying to do is initializing an array count[] and just like hashing it increments the number of coin[j] whenever min is found, i.e count[coin[j]]++ . But this is not working the way I wanted because it adds the coin every time it finds min corresponding to coin[j]. Hence the number is not the final count of coin in the final answer.

Here is the code:

void makeChange(int coin[], int n, int value)
{
    int i, j;
    int min_coin[MAX];
    int min;

    int count[MAX];
    min_coin[0] = 0;

    for (i=1; i <= value; i++)
    {
            min = 999;
            for (j = 0; j<n; j++)
            {
                    if (coin[j] <= i)
                    {
                            if (min > min_coin[i-coin[j]]+1)
                            {
                                    min = min_coin[i-coin[j]]+1;
                                    count[coin[j]]++;
                            }
                    }
            }
            min_coin[i] = min;
    }

    printf("minimum coins required %d \n", min_coin[value]);

}

Answer 1

You have to keep an extra, two-dinemsional array to store the coin count for each value and each coin denomination.

When you assign a new minimum in your inner loop, copy all coin counts from i - coin[j] to i and then increment min_count[i][j]. The number of coins needed is then in coin_count[value].

Answer 2

As you already noted, the bottom-up solution adds the coin every time, not only when i == value, but if you want to know the count of coins when i == value, it depends on the the counts of coins of sub-problems, so we need store previous computations with a 2-D array:

#include <stdio.h>

#define MAX 1000
#define COIN_ARRAY_SIZE 4

void makeChange(int coin[], int n, int value)
{
    int i, j, k;
    int min_coin[MAX];

    int count[MAX + 1][COIN_ARRAY_SIZE] = {0}; // zeroing
    int min;

    //int count[MAX];
    min_coin[0] = 0;

    for (i=1; i <= value; i++)
    {
        min = 999;
        for (j = 0; j<n; j++)
        {
            if (coin[j] <= i)
            {
                if (min > min_coin[i-coin[j]]+1)
                {
                    min = min_coin[i-coin[j]]+1;
                    for(k = 0; k < n; ++k)
                    {
                        count[i][k] = count[i-coin[j]][k]; // copy coin counts when value=i-coin[j]
                    }
                    count[i][j]++; // use a coin[j], increase the count
                }
            }
        }
        min_coin[i] = min;
    }

    printf("minimum coins required %d \n", min_coin[value]);
    for(int i = 0; i < COIN_ARRAY_SIZE; ++i)
        printf("%d: %d\n", coin[i], count[value][i]);

}

Driver program to test above function:

int main()
{
    int coin[COIN_ARRAY_SIZE] = {5,3,2,1};
    makeChange(coin, 4, 8);
    makeChange(coin, 4, 10);
};