Coin change Problem ( C++ Solution)

coins Suppose we need to make change for 67¢. We want to do this using the fewest number of coins possible. Pennies, nickels, dimes and quarters are available.

Formal description of the problem is as follows:

Let D = {d1, d2, …, dk} be a finite set of distinct coin denominations.

Example: d1 = 25¢, d2 = 10¢, d3 = 5¢, and d4 = 1¢.
• We can assume each di is an integer and d1 > d2 > … > dk.
• Each denomination is available in unlimited quantity.

  • The Coin-Changing problem:
    – Make change for n cents, using a minimum total number of coins.
    – Assume that dk = 1 so that there is always a solution.

Solution using dynamic programming is as follows:

  • Let D = {d1, d2, …, dk} be the set of coin denominations, arranged such that d1 = 1¢. As before, the problem is to make change for n cents using the fewest number of coins.
  • Use a table C[1..k, 0..n]:
    – C[i, j] is the smallest number of coins used to make change for j cents, using only coins d1, d2, …, di.
    – The overal number of coins (the final optimal solution) will be computed in C[k, n].
#include <vector>
#include <iostream>
#include <string>
int compute_change(std::vector<int> &d, int size) {
    int k = (int)d.size();
    std::vector<std::vector<int> > table(k , std::vector<int>(size + 1));
    for ( int row = 0; row < k ; row++) 
        table[row][0]  = 0;    
    for ( int col = 0; col <= size ; col++) 
        table[0][col]  = col;
    for ( int row = 1 ; row < k; row++) {
        for ( int col = 1 ; col <= size; col++) {
            if ( col < d[row] )  
                table[row][col] = table[row - 1][col];
            else 
                table[row][col] = std::min(table[row - 1][col], 1 + table[row][col - d[row]]);
        }
    }
    return table[k - 1][size - 1];
}
int main ( int argc, char **argv) {
    int points[] = { 1, 2, 3, 17, 23, 42, 98};
    std::vector<int> d (points, points + sizeof(points) / sizeof(int));
    int solution =  compute_change(d,2349 );
    return 0;
}

Code can be downloaded from here

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s