10.13

1

1. 20 x 1
2. 1 x 6 + 14 x 1
3. 2 x 6 + 8 x 1
4. 3 x 6 + 2 x 1
5. 1 x 10 + 10 x 1
6. 1 x 10 + 1 x 6 + 4 x 1
7. 2 x 10

2

More generally:

1. there is always one way of making zero from any set of denominations;
2. there is one way of making any non-zero sum from one denomination provided that the sum is evenly divisible by the denomination;
3. for larger sets of denominations, the number of ways to make a sum S from a set D = { a, b, ... m, n } where Di < Dj for i < j, is the sum of the ways to make S, S - n, ... S - xn from D' = { a, b, c, ... m }.

Implementation in C:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

static unsigned
make_change (unsigned sum, unsigned *coins, size_t nr_coins)
  {
  unsigned **table = malloc (nr_coins * sizeof *table);

  assert (table != NULL);

  for (size_t c = 0; c < nr_coins; ++c)
    {
    table[c] = malloc ((1 + sum) * sizeof *table[c]);

    assert (table[c] != NULL);

    if (c == 0)
      {
      /*
       * No. of ways of making s from coins[0]: 1 if s is evenly divisible by
       * coins[0], 0 otherwise.
       */
      for (unsigned s = 0; s <= sum; ++s)
        table[0][s] = s % coins[0] == 0;
      }
    else
      {
      /*
       * One way of making 0 from { coins[0] .. coins[c] }: the empty set.
       */
      table[c][0] = 1;

      /*
       * No. of ways of making s from { coins[0] .. coins[c] }: no. of ways of
       * making s - n * coins[c] for n > 0 and s >= n * coins[c]
       * from { coins[0] .. coins[c - 1] }
       */
      for (unsigned s = 1; s <= sum; ++s)
        for (unsigned n = 0; n * coins[c] <= s; n ++)
          table[c][s] += table[c - 1][s - (n * coins[c])];
      }
    }

  unsigned rv = table[nr_coins - 1][sum];

  for (size_t c = 0; c < nr_coins; ++c)
    free (table[c]);

  free (table);

  return rv;
  }

static int
cmp_coins (const void *a, const void *b)
  {
  return (*(unsigned *) a > *(unsigned *) b)
       - (*(unsigned *) a < *(unsigned *) b);
  }

int
main (int argc, char **argv)
  {
  if (argc < 3)
    exit (EXIT_FAILURE);

  unsigned sum = atoi (argv[1]);

  size_t nr_coins = argc - 2;

  unsigned *coins = malloc (nr_coins * sizeof *coins);

  assert (coins != NULL);

  for (int i = 2; i < argc; ++i)
    coins[i - 2] = atoi (argv[i]);

  qsort (coins, nr_coins, sizeof *coins, cmp_coins);

  fprintf (stderr, "%u\n", make_change (sum, coins, nr_coins));

  free (coins);

  exit (EXIT_SUCCESS);
  }

Back to Chapter 10