Azazel: Created page with "==== 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 o..."

2016-12-22T14:07:17Z

Created page with "==== 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 o..."

New page

==== 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);
}

TADM2E 8.7 - Revision history

Azazel: Created page with "==== 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 o..."