Difference between pages "7.17" and "10.13"
(Difference between pages)
Jump to navigation
Jump to search
(Created page with "1) We can determine that leafs should never be included into the cover. Therefore all leaves should be unmarked, which means that all of their parents should be marked. Now we...") |
(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...") |
||
Line 1: | Line 1: | ||
− | 1 | + | ==== 1 ==== |
− | 2 | + | # 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: | ||
− | Back to [[Chapter | + | # 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); | ||
+ | } | ||
+ | |||
+ | |||
+ | Back to [[Chapter 10]] |
Latest revision as of 01:17, 21 September 2020
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); }
Back to Chapter 10