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