# TADM2E 8.7

From Algorithm Wiki

#### 1

- 20 x 1
- 1 x 6 + 14 x 1
- 2 x 6 + 8 x 1
- 3 x 6 + 2 x 1
- 1 x 10 + 10 x 1
- 1 x 10 + 1 x 6 + 4 x 1
- 2 x 10

#### 2

More generally:

- there is always one way of making zero from any set of denominations;
- there is one way of making any non-zero sum from one denomination provided that the sum is evenly divisible by the denomination;
- 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); }