Difference between pages "7.17" and "10.13"

From The Algorithm Design Manual Solution Wiki
(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) 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 remove all leaves from the tree and all of their parents, together with all of their edges. We then repeat this process on the modified tree.
+
==== 1 ====
  
2) We consider again the leafs, each is degree 1. For each leaf, if we consider its parent, its degree is the number of children + 1. It means that we have to choose between removing the n children of degree one or the parent of degree n+1. We remove the parent, mark the leafs as included, and recurse as in 1) above.
+
# 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
  
3) We know we will be able to remove at most one every other node, so we use a two-coloring technique (Red/Black) and perform a post-order traversal. Let's assume we will remove all the Black node.  When we process a node, we also store with each node the sum over its immediate children of the respective Red and Black weight for the subtree.
+
==== 2 ====
If not all of the children are Red, we need to mark the current node as Red. But we also have the option to reverse the coloring of all the Red-children's subtree. So we look at the sum over the red-children for
 
Red and Black, and compare the difference of these sum to the current node's weight. If the current node's weight is above, we swap the coloring for these subtree.
 
The current node will record the Black and Red sum of its children's subtree, and add its own weight to its color.
 
  
 +
More generally:
  
Back to [[Chapter 7]]
+
# 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

  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