[C] Dynamic Programming 101: Change for a Dollar
We describe an efficient dynamic programming algorithm to compute the number of ways that one might make change for a dollar. The answer, assuming pennies, nickles, dimes, quarters, and half-dollars? Two hundred ninety two.
Change for a Dollar
The key idea of dynamic programming is to construct a current solution from previously computed solutions. In this case, we consider solutions to exist for each value less than the current. So, for $1, we assume that we know solutions for 99 cents, 98 cents, etc. Here, a solution is a collection of vectors with the number of each type of coin in each component. For example, (4,0,2,1,1) is 4 pennies, 0 nickles, 2 dimes, 1 quarter, and 1 half dollar and has value 99 cents. (4,0,2,1,1) is one of many ways in which one might make change for 99 cents.
Returning to the case of $1, we ask which previous solutions are applicable. If we have a solution for 99 cents, then we could add a penny to each of the tuples in the collection for 99 cents. If we have a solution for 95 cents, then we could add a nickle to each of the tuples in the collection for 95 cents. In fact, for a $1, we are interested in previous solutions that look back by the amount of a single coin: 99 cents (lookback one penny), 95 cents (lookback one nickle), 90 cents (lookback one dime), 75 cents (lookback one quarter), and 50 cents (lookback one half-dollar).
The current solution, then, is to consider each tuple from the applicable lookbacks and add the respective coin. However, this can result in duplicate tuples. Consider making change for 6 cents using this approach. The applicable lookbacks are a penny and a nickle. The penny lookback uses each 5 cent tuple and adds a penny: (5,0,0,0,0) + (1,0,0,0,0) and (0,1,0,0,0) + (1,0,0,0,0). The nickle lookback uses each 1 cent tuple and adds a nickle: (1,0,0,0,0) + (0,1,0,0,0). This produces (6,0,0,0,0), (1,1,0,0,0), and (1,1,0,0,0). If we reduce this to unique tuples, we get the expected solution for 6 cents: there are two tuples and they are (6,0,0,0,0) and (1,1,0,0,0). In the code, we use a binary tree to enforce uniqueness.
main.c
This defines the auxiliary variables and computes increasingly larger-value solutions.
Why write in C? For practice.
/assets/2016-10-06-change-for-a-dollar/main.c:
/*
* main.c
*
* Created on: Oct 6, 2016
* Author: Dustin Lennon
* Email: dustin@inferentialist.com
*/
#include <stdio.h>
#include "soln.h"
#include "coin_vec.h"
/* function prototypes */
void cv_tree_node_to_soln(soln_t* s, cv_tree_node_t* node);
int main(int argc, char** argv)
{
int i,j,k;
int lookback;
// Denomination of each coin
coin_vec_t values, tmp_cv;
set_coin_vec(&values, 1, 5, 10, 25, 50);
// Indicator functions: used to add a particular coin to a previous coin_vec
coin_vec_t coin_ind[NCOINS];
set_coin_vec(&coin_ind[0], 1, 0, 0, 0, 0);
set_coin_vec(&coin_ind[1], 0, 1, 0, 0, 0);
set_coin_vec(&coin_ind[2], 0, 0, 1, 0, 0);
set_coin_vec(&coin_ind[3], 0, 0, 0, 1, 0);
set_coin_vec(&coin_ind[4], 0, 0, 0, 0, 1);
// coin_vec tree: maintains unique coin_vecs
cv_tree_t cv_tree;
cv_tree_init(&cv_tree);
// how far should we go? 100 == $1
const int sz = 100;
/* create and initialize the solutions array */
soln_t soln[sz+1];
for(i=0; i<=sz; i++)
{
init_soln(&soln[i]);
}
/* initialize the base-case */
malloc_soln(&soln[0], 1);
set_coin_vec(&(soln[0].p_coin_vec[0]), 0, 0, 0, 0, 0);
/* loop through each value between 0 cents and 'sz' cents */
for(i=1; i<=sz; i++)
{
/* the current solution uses several previous solutions; in particular, solutions
* associated with values that are one coin-value behind, e.g. [26] would combine
* solutions from [25], [21], [16], [1] */
for(j=0; j<NCOINS; j++)
{
lookback = values.counts[j];
if( i - lookback >= 0 )
{
/* for each previous solution, add the respective coin to bring the value up
* to the current level; keep the unique coin_vec's
*/
soln_t* s = &soln[ i - lookback ];
for(k=0; k < s->nrow; k++)
{
add_coin_vec(&tmp_cv, &(s->p_coin_vec[k]), &coin_ind[j]);
cv_tree_insert(&cv_tree, &tmp_cv);
}
}
}
/* copy from the tree to the array */
malloc_soln(&soln[i], cv_tree.count);
cv_tree_node_to_soln(&soln[i], cv_tree.root);
/* print out the intermediate solution */
printf("%d (%d):\n", i, soln[i].nrow);
print_soln(&soln[i]);
printf("\n");
cv_tree_empty(&cv_tree);
}
/* clean up dynamically allocated memory */
free_soln(&soln[0]);
for(i=0; i<=sz; i++)
{
free_soln(&soln[i]);
}
return 0;
}
/* recursive function to transfer the coin_vecs from the tree to the current soln */
void cv_tree_node_to_soln(soln_t* s, cv_tree_node_t* node)
{
if(node == NULL)
return;
cv_tree_node_to_soln(s, node->l);
cv_tree_node_to_soln(s, node->r);
int idx = node->idx;
copy_coin_vec( &(s->p_coin_vec[idx]), &(node->cv) );
}
coin_vec.[ch]
These files define the coin-count tuples and provide helper functions for manipulating them. The cv_tree_t struct is a binary tree that stores unique tuples.
/assets/2016-10-06-change-for-a-dollar/coin_vec.h:
/*
* coinvec.h
*
* Created on: Oct 6, 2016
* Author: Dustin Lennon
* Email: dustin@inferentialist.com
*/
#ifndef COINVEC_H_
#define COINVEC_H_
#define NCOINS 5
typedef struct
{
/* penny, nickel, dime, quarter, half-dollar */
int counts[NCOINS];
} coin_vec_t;
void set_coin_vec(coin_vec_t* src, int p, int n, int d, int q, int hd);
void copy_coin_vec(coin_vec_t* dest, coin_vec_t* src);
void add_coin_vec(coin_vec_t* dest, coin_vec_t* src, coin_vec_t* inc);
int cmp_coin_vec(coin_vec_t* lhs, coin_vec_t* rhs);
typedef struct cv_tree_node_t cv_tree_node_t;
typedef struct cv_tree_t cv_tree_t;
/* wrapper object for coin_vec tree */
struct cv_tree_t
{
cv_tree_node_t* root;
int count;
};
/* internal data structure for tree */
struct cv_tree_node_t
{
cv_tree_node_t* l, *r;
coin_vec_t cv;
/* idx: a unique id for each node added to the tree */
int idx;
};
void cv_tree_init(cv_tree_t* t);
void cv_tree_insert(cv_tree_t* t, coin_vec_t* cv);
void cv_tree_empty(cv_tree_t* t);
cv_tree_node_t* cv_tree_node_new(coin_vec_t* cv, int* idx);
cv_tree_node_t* cv_tree_node_insert(cv_tree_node_t* node, coin_vec_t* cv, int* idx);
void cv_tree_node_empty(cv_tree_node_t* node);
#endif /* COINVEC_H_ */
/assets/2016-10-06-change-for-a-dollar/coin_vec.c:
/*
* coin_vec.c
*
* Created on: Oct 6, 2016
* Author: Dustin Lennon
* Email: dustin@inferentialist.com
*/
#include <stdlib.h>
#include "coin_vec.h"
#define PENNY 0
#define NICKEL 1
#define DIME 2
#define QUARTER 3
#define HALFDOLLAR 4
/* Set the coin vector.
* NOTE - this should be the only place in the code where the
* coin counts are set individually. */
void set_coin_vec(coin_vec_t* src, int p, int n, int d, int q, int hd)
{
src->counts[PENNY] = p;
src->counts[NICKEL] = n;
src->counts[DIME] = d;
src->counts[QUARTER] = q;
src->counts[HALFDOLLAR] = hd;
}
/* Copy a coin_vec from src to dest */
void copy_coin_vec(coin_vec_t* dest, coin_vec_t* src)
{
for(int i=0; i<NCOINS; i++)
{
dest->counts[i] = src->counts[i];
}
}
/* Add a coin_vec to src and store in dest */
void add_coin_vec(coin_vec_t* dest, coin_vec_t* src, coin_vec_t* inc)
{
for(int i=0; i<NCOINS; i++)
{
dest->counts[i] = src->counts[i] + inc->counts[i];
}
}
/* Comparison function for two coin vectors */
int cmp_coin_vec(coin_vec_t* lhs, coin_vec_t* rhs)
{
for(int i=0; i<NCOINS; i++)
{
if(lhs->counts[i] < rhs->counts[i])
return -1;
if(lhs->counts[i] > rhs->counts[i])
return 1;
}
return 0;
}
/* initialize the coin_vec tree */
void cv_tree_init(cv_tree_t* t)
{
t->count = 0;
t->root = NULL;
}
/* insert a coin_vec into the tree (wrapper) */
void cv_tree_insert(cv_tree_t* t, coin_vec_t* cv)
{
t->root = cv_tree_node_insert(t->root, cv, &(t->count));
}
/* clean up the tree and free the underlying memory (wrapper) */
void cv_tree_empty(cv_tree_t* t)
{
cv_tree_node_empty(t->root);
t->count = 0;
t->root = NULL;
}
/* create a new node in the tree, set the coin_vec, and an index */
cv_tree_node_t* cv_tree_node_new(coin_vec_t* cv, int* idx)
{
cv_tree_node_t* node = (cv_tree_node_t*) malloc(sizeof(cv_tree_node_t));
copy_coin_vec(&(node->cv), cv);
node->idx = *idx;
/* bump the index; it's a pointer to the tree->count */
*idx = *idx + 1;
node->l = NULL;
node->r = NULL;
return node;
}
/* recursively insert a coin_vec into the tree */
cv_tree_node_t* cv_tree_node_insert(cv_tree_node_t* node, coin_vec_t* cv, int* idx)
{
if(node == NULL)
{
return cv_tree_node_new(cv, idx);
}
int cmp = cmp_coin_vec(&node->cv, cv);
if( cmp == -1 )
{
node->l = cv_tree_node_insert(node->l, cv, idx);
}
else if (cmp == 1)
{
node->r = cv_tree_node_insert(node->r, cv, idx);
}
return node;
}
/* recursively clean up the tree */
void cv_tree_node_empty(cv_tree_node_t* node)
{
if(node == NULL)
return;
cv_tree_node_empty(node->l);
cv_tree_node_empty(node->r);
free(node);
}
soln.[ch]
These files define the soln_t struct and helper functions.
/assets/2016-10-06-change-for-a-dollar/soln.h:
/*
* soln.h
*
* Created on: Oct 6, 2016
* Author: Dustin Lennon
* Email: dustin@inferentialist.com
*/
#ifndef SOLN_H_
#define SOLN_H_
#include "coin_vec.h"
typedef struct
{
coin_vec_t* p_coin_vec;
int nrow;
} soln_t;
void print_soln(soln_t* s);
void init_soln(soln_t* s);
void malloc_soln(soln_t* s, int nrow);
void free_soln(soln_t* s);
#endif /* SOLN_H_ */
/assets/2016-10-06-change-for-a-dollar/soln.c:
/*
* soln.c
*
* Created on: Oct 6, 2016
* Author: Dustin Lennon
* Email: dustin@inferentialist.com
*/
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "coin_vec.h"
#include "soln.h"
/* print a solution */
void print_soln(soln_t* s)
{
int nrow = s->nrow;
for(int i=0; i<nrow; i++)
{
coin_vec_t* cv = &(s->p_coin_vec[i]);
printf("(%d", cv->counts[0]);
for(int j=1; j<NCOINS; j++)
{
printf(",%d", cv->counts[j]);
}
printf(")\n");
}
}
/* initialize a solution */
void init_soln(soln_t* s)
{
s->nrow = 0;
s->p_coin_vec = NULL;
}
/* allocate the memory for nrow coin_vec tuples */
void malloc_soln(soln_t* s, int nrow)
{
if(s->p_coin_vec != NULL)
{
assert("error: malloc'd a soln_t that was already malloc'd");
}
s->p_coin_vec = (coin_vec_t*) malloc(nrow * sizeof(coin_vec_t));
s->nrow = nrow;
for(int i=0; i<nrow; i++)
{
memset(s->p_coin_vec[i].counts, 0, NCOINS * sizeof(int));
}
}
/* free the memory for the coin_vec tuples */
void free_soln(soln_t* s)
{
if(s->p_coin_vec == NULL)
{
assert("error: free'd a soln_t that was never malloc'd");
}
free(s->p_coin_vec);
s->nrow = 0;
s->p_coin_vec = NULL;
}
Dollar Tuples
These tuples are coin counts of the form (pennies, nickles, dimes, quarters, half-dollars).
- (100,0,0,0,0)
- (95,1,0,0,0)
- (90,2,0,0,0)
- (90,0,1,0,0)
- (85,3,0,0,0)
- (85,1,1,0,0)
- (80,4,0,0,0)
- (80,2,1,0,0)
- (80,0,2,0,0)
- (75,5,0,0,0)
- (75,3,1,0,0)
- (75,1,2,0,0)
- (75,0,0,1,0)
- (70,6,0,0,0)
- (70,4,1,0,0)
- (70,2,2,0,0)
- (70,1,0,1,0)
- (70,0,3,0,0)
- (65,7,0,0,0)
- (65,5,1,0,0)
- (65,3,2,0,0)
- (65,2,0,1,0)
- (65,1,3,0,0)
- (65,0,1,1,0)
- (60,8,0,0,0)
- (60,6,1,0,0)
- (60,4,2,0,0)
- (60,3,0,1,0)
- (60,2,3,0,0)
- (60,1,1,1,0)
- (60,0,4,0,0)
- (55,9,0,0,0)
- (55,7,1,0,0)
- (55,5,2,0,0)
- (55,4,0,1,0)
- (55,3,3,0,0)
- (55,2,1,1,0)
- (55,1,4,0,0)
- (55,0,2,1,0)
- (50,10,0,0,0)
- (50,8,1,0,0)
- (50,6,2,0,0)
- (50,5,0,1,0)
- (50,4,3,0,0)
- (50,3,1,1,0)
- (50,2,4,0,0)
- (50,1,2,1,0)
- (50,0,5,0,0)
- (50,0,0,2,0)
- (50,0,0,0,1)
- (45,11,0,0,0)
- (45,9,1,0,0)
- (45,7,2,0,0)
- (45,6,0,1,0)
- (45,5,3,0,0)
- (45,4,1,1,0)
- (45,3,4,0,0)
- (45,2,2,1,0)
- (45,1,5,0,0)
- (45,1,0,2,0)
- (45,1,0,0,1)
- (45,0,3,1,0)
- (40,12,0,0,0)
- (40,10,1,0,0)
- (40,8,2,0,0)
- (40,7,0,1,0)
- (40,6,3,0,0)
- (40,5,1,1,0)
- (40,4,4,0,0)
- (40,3,2,1,0)
- (40,2,5,0,0)
- (40,2,0,2,0)
- (40,2,0,0,1)
- (40,1,3,1,0)
- (40,0,6,0,0)
- (40,0,1,2,0)
- (40,0,1,0,1)
- (35,13,0,0,0)
- (35,11,1,0,0)
- (35,9,2,0,0)
- (35,8,0,1,0)
- (35,7,3,0,0)
- (35,6,1,1,0)
- (35,5,4,0,0)
- (35,4,2,1,0)
- (35,3,5,0,0)
- (35,3,0,2,0)
- (35,3,0,0,1)
- (35,2,3,1,0)
- (35,1,6,0,0)
- (35,1,1,2,0)
- (35,1,1,0,1)
- (35,0,4,1,0)
- (30,14,0,0,0)
- (30,12,1,0,0)
- (30,10,2,0,0)
- (30,9,0,1,0)
- (30,8,3,0,0)
- (30,7,1,1,0)
- (30,6,4,0,0)
- (30,5,2,1,0)
- (30,4,5,0,0)
- (30,4,0,2,0)
- (30,4,0,0,1)
- (30,3,3,1,0)
- (30,2,6,0,0)
- (30,2,1,2,0)
- (30,2,1,0,1)
- (30,1,4,1,0)
- (30,0,7,0,0)
- (30,0,2,2,0)
- (30,0,2,0,1)
- (25,15,0,0,0)
- (25,13,1,0,0)
- (25,11,2,0,0)
- (25,10,0,1,0)
- (25,9,3,0,0)
- (25,8,1,1,0)
- (25,7,4,0,0)
- (25,6,2,1,0)
- (25,5,5,0,0)
- (25,5,0,2,0)
- (25,5,0,0,1)
- (25,4,3,1,0)
- (25,3,6,0,0)
- (25,3,1,2,0)
- (25,3,1,0,1)
- (25,2,4,1,0)
- (25,1,7,0,0)
- (25,1,2,2,0)
- (25,1,2,0,1)
- (25,0,5,1,0)
- (25,0,0,3,0)
- (25,0,0,1,1)
- (20,16,0,0,0)
- (20,14,1,0,0)
- (20,12,2,0,0)
- (20,11,0,1,0)
- (20,10,3,0,0)
- (20,9,1,1,0)
- (20,8,4,0,0)
- (20,7,2,1,0)
- (20,6,5,0,0)
- (20,6,0,2,0)
- (20,6,0,0,1)
- (20,5,3,1,0)
- (20,4,6,0,0)
- (20,4,1,2,0)
- (20,4,1,0,1)
- (20,3,4,1,0)
- (20,2,7,0,0)
- (20,2,2,2,0)
- (20,2,2,0,1)
- (20,1,5,1,0)
- (20,1,0,3,0)
- (20,1,0,1,1)
- (20,0,8,0,0)
- (20,0,3,2,0)
- (20,0,3,0,1)
- (15,17,0,0,0)
- (15,15,1,0,0)
- (15,13,2,0,0)
- (15,12,0,1,0)
- (15,11,3,0,0)
- (15,10,1,1,0)
- (15,9,4,0,0)
- (15,8,2,1,0)
- (15,7,5,0,0)
- (15,7,0,2,0)
- (15,7,0,0,1)
- (15,6,3,1,0)
- (15,5,6,0,0)
- (15,5,1,2,0)
- (15,5,1,0,1)
- (15,4,4,1,0)
- (15,3,7,0,0)
- (15,3,2,2,0)
- (15,3,2,0,1)
- (15,2,5,1,0)
- (15,2,0,3,0)
- (15,2,0,1,1)
- (15,1,8,0,0)
- (15,1,3,2,0)
- (15,1,3,0,1)
- (15,0,6,1,0)
- (15,0,1,3,0)
- (15,0,1,1,1)
- (10,18,0,0,0)
- (10,16,1,0,0)
- (10,14,2,0,0)
- (10,13,0,1,0)
- (10,12,3,0,0)
- (10,11,1,1,0)
- (10,10,4,0,0)
- (10,9,2,1,0)
- (10,8,5,0,0)
- (10,8,0,2,0)
- (10,8,0,0,1)
- (10,7,3,1,0)
- (10,6,6,0,0)
- (10,6,1,2,0)
- (10,6,1,0,1)
- (10,5,4,1,0)
- (10,4,7,0,0)
- (10,4,2,2,0)
- (10,4,2,0,1)
- (10,3,5,1,0)
- (10,3,0,3,0)
- (10,3,0,1,1)
- (10,2,8,0,0)
- (10,2,3,2,0)
- (10,2,3,0,1)
- (10,1,6,1,0)
- (10,1,1,3,0)
- (10,1,1,1,1)
- (10,0,9,0,0)
- (10,0,4,2,0)
- (10,0,4,0,1)
- (5,19,0,0,0)
- (5,17,1,0,0)
- (5,15,2,0,0)
- (5,14,0,1,0)
- (5,13,3,0,0)
- (5,12,1,1,0)
- (5,11,4,0,0)
- (5,10,2,1,0)
- (5,9,5,0,0)
- (5,9,0,2,0)
- (5,9,0,0,1)
- (5,8,3,1,0)
- (5,7,6,0,0)
- (5,7,1,2,0)
- (5,7,1,0,1)
- (5,6,4,1,0)
- (5,5,7,0,0)
- (5,5,2,2,0)
- (5,5,2,0,1)
- (5,4,5,1,0)
- (5,4,0,3,0)
- (5,4,0,1,1)
- (5,3,8,0,0)
- (5,3,3,2,0)
- (5,3,3,0,1)
- (5,2,6,1,0)
- (5,2,1,3,0)
- (5,2,1,1,1)
- (5,1,9,0,0)
- (5,1,4,2,0)
- (5,1,4,0,1)
- (5,0,7,1,0)
- (5,0,2,3,0)
- (5,0,2,1,1)
- (0,20,0,0,0)
- (0,18,1,0,0)
- (0,16,2,0,0)
- (0,15,0,1,0)
- (0,14,3,0,0)
- (0,13,1,1,0)
- (0,12,4,0,0)
- (0,11,2,1,0)
- (0,10,5,0,0)
- (0,10,0,2,0)
- (0,10,0,0,1)
- (0,9,3,1,0)
- (0,8,6,0,0)
- (0,8,1,2,0)
- (0,8,1,0,1)
- (0,7,4,1,0)
- (0,6,7,0,0)
- (0,6,2,2,0)
- (0,6,2,0,1)
- (0,5,5,1,0)
- (0,5,0,3,0)
- (0,5,0,1,1)
- (0,4,8,0,0)
- (0,4,3,2,0)
- (0,4,3,0,1)
- (0,3,6,1,0)
- (0,3,1,3,0)
- (0,3,1,1,1)
- (0,2,9,0,0)
- (0,2,4,2,0)
- (0,2,4,0,1)
- (0,1,7,1,0)
- (0,1,2,3,0)
- (0,1,2,1,1)
- (0,0,10,0,0)
- (0,0,5,2,0)
- (0,0,5,0,1)
- (0,0,0,4,0)
- (0,0,0,2,1)
- (0,0,0,0,2)