# 10.13

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

/*
* No. of ways of making s from { coins .. coins[c] }: no. of ways of
* making s - n * coins[c] for n > 0 and s >= n * coins[c]
* from { coins .. 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);

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