CLRS-Cpp-Implementations-Chapter-15

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

namespace CLRS
{
  template <std::size_t n>
  void optimal_bst(double (&p)[n], double (&q)[n],
		   double (&e)[n + 1][n], std::size_t(&root)[n][n])
  {
    double w[n + 1][n];
    for(std::size_t i = 1; i <= n; ++i)
      {
	e[i][i - 1] = q[i - 1];
	w[i][i - 1] = q[i - 1];
      }
    for(std::size_t l = 1; l != n; ++l)
      for(std::size_t i = 1; i != n - l + 1; ++i)
	{
	  std::size_t j = i + l - 1;
	  e[i][j] = 1000;
	  w[i][j] = w[i][j - 1] + p[j] + q[j];
	  for(std::size_t r = i; r <= j; ++r)
	    {
	      double t = e[i][r - 1]
		+ e[r + 1][j] + w[i][j];
	      if(t < e[i][j])
		{
		  e[i][j] = t;
		  root[i][j] = r;
		}
	    }
	}
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

namespace CLRS
{
  template <typename t, std::size_t m, std::size_t n>
  void lcs_length(t (&x)[m], t (&y)[n],
		  char (&b)[m + 1][n + 1], t (&c)[m + 1][n + 1])
  {
    for(std::size_t i = 1; i != m; ++i)
      c[i][0] = 0;
    for(std::size_t j = 0; j != n; ++j)
      c[0][j] = 0;
    for(std::size_t i = 1; i <= m; ++i)
      for(std::size_t j = 1; j <= n; ++j)
	{
	  if(x[i - 1] == y[j - 1])
	    {
	      c[i][j] = c[i - 1][j - 1] + 1;
	      b[i][j] = 'c';
	    }
	  else if(c[i - 1][j] >= c[i][j - 1])
	    {
	      c[i][j] = c[i - 1][j];
	      b[i][j] = 'u';
	    }
	  else
	    {
	      c[i][j] = c[i][j - 1];
	      b[i][j] = 'l';
	    }
	}
  }

  template <typename t, std::size_t m, std::size_t n>
  void print_lcs(char (&b)[m][n], t (&x)[m - 1],
		 std::size_t i, std::size_t j)
  {
    if(i == 0 || j == 0)
      return;
    if(b[i][j] == 'c')
      {
	print_lcs(b, x, i - 1, j - 1);
	std::cout << x[i - 1];
      }
    else if(b[i][j] == 'u')
      print_lcs(b, x, i - 1, j);
    else
      print_lcs(b, x, i, j - 1);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

namespace CLRS
{
  template <std::size_t m>
  unsigned memoized_cut_rod_aux(const unsigned (&)[m],
				unsigned, long *);
  template <std::size_t m>
  unsigned memoized_cut_rod(const unsigned (&prices)[m],
			    unsigned n)
  {
    long r[n + 1];
    for(std::size_t i = 0; i <= n; ++i)
      r[i] = -1;
    return memoized_cut_rod_aux(prices, n, r);
  }

  template <std::size_t m>
  unsigned memoized_cut_rod_aux(const unsigned (&prices)[m],
				unsigned n, long *r)
  {
    if(r[n] >= 0)
      return r[n];
    unsigned q = 0;
    if(n == 0)
      q = 0;
    else
      {
	for(unsigned i = 1; i <= n && i < m; ++i)
	  {
	    q = std::max(q, prices[i] +
			 memoized_cut_rod_aux(prices, n - i, r));
	  }
      }
    r[n] = q;
    return q;
  }

  template <std::size_t m>
  unsigned bottom_up_cut_rod(const unsigned (&prices)[m], unsigned n)
  {
    unsigned r[n + 1];
    r[0] = 0;
    for(std::size_t j = 1; j <= n; ++j)
      {
	unsigned q = 0;
	for(std::size_t i = 1; i <= j && i < m; ++i)
	  q = std::max(q, prices[i] + r[j - i]);
	r[j] = q;
      }
    return r[n];
  }

  template <std::size_t m>
  void extended_bottom_up_cut_rod(const unsigned (&prices)[m],
				  unsigned n,
				  unsigned *r,
				  std::size_t *s)
  {
    r[0] = 0;
    for(std::size_t j = 1; j <= n; ++j)
      {
	unsigned q = 0;
	for(std::size_t i = 1; i <= j && i < m; ++i)
	  {
	    if(q < prices[i] + r[j - i])
	      {
		q = prices[i] + r[j - i];
		s[j] = i;
	      }
	  }
	r[j] = q;
      }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

namespace CLRS
{
  constexpr unsigned CUT_ROD_PRICES[11] =
    {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

  template <std::size_t m>
  unsigned recursive_cut_rod(const unsigned (&prices)[m],
			     unsigned n)
  {
    if(n == 0)
      return 0;
    unsigned q = 0;
    for(unsigned i = 1; i <= n && i < m; ++i)
      q = std::max(q, prices[i] +
		   recursive_cut_rod(prices, n - i));
    return q;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

namespace CLRS
{
  template <std::size_t n>
  void matrix_chain_order(unsigned (&p)[n],
			  unsigned (&m)[n][n],
			  std::size_t (&s)[n][n])
  {
    std::size_t x = n - 1;
    for(std::size_t i = 1; i <= x; ++i)
      m[i][i] = 0;
    for(std::size_t l = 2; l <= x; ++l)
      {
	for(std::size_t i = 1; i <= x - l + 1; ++i)
	  {
	    std::size_t j = i + l - 1;
	    m[i][j] = -1;
	    for(std::size_t k = i; k <= j - 1; ++k)
	      {
		unsigned q = m[i][k] + m[k + 1][j]+
		  p[i - 1] * p[k] * p[j];
		if(q < m[i][j])
		  {
		    m[i][j] = q;
		    s[i][j] = k;
		  }
	      }
	  }
      }
  }

  template <std::size_t n>
  void print_optimal_parens(const unsigned (&s)[n][n],
			    unsigned i, unsigned j)
  {
    if(i == j)
      std::cout << "A" << i;
    else
      {
	std::cout << "(";
	print_optimal_parens(s, i, s[i][j]);
	print_optimal_parens(s, s[i][j] + 1, j);
	std::cout << ")";
      }
  }

  template <std::size_t n>
  unsigned lookup_chain(unsigned (&m)[n][n],
			unsigned (&p)[n],
			std::size_t i,
			std::size_t j)
  {
    if(m[i][j] < -1)
      return m[i][j];
    if(i == j)
      m[i][j] = 0;
    else
      {
	for(std::size_t k = i; k <= j - 1; ++k)
	  {
	    std::size_t q = lookup_chain(m, p, i, k)
	      + lookup_chain(m, p, k + 1, j)
	      + p[i - 1]*p[k]*p[j];
	    if(q < m[i][j])
	      m[i][j] = q;
	  }
      }
    return m[i][j];
  }

  template <std::size_t n>
  unsigned memoized_matrix_chain(unsigned (&p)[n])
  {
    std::size_t x = n - 1;
    unsigned m[n][n];
    for(std::size_t i = 0; i != n; ++i)
      for(std::size_t j = 0; j != n; ++j)
	m[i][j] = -1;
    return lookup_chain(m, p, 1, x);
  }
}