CSC301.01 2015F, Class 33: Dynamic Programming (1)
==================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* The Stamps problem.
* Dynamic programming.
* The Knapsack problem.

Preliminaries
-------------

### Admin

* HW Due!
* Thanks for being good for Monday's visitor.
* Yes, I am alive.  The rumors of my death are one of those fascinating
  aspects of Social Media.
* The Monday after break we are (hopefully) allowed to talk about the things
  that have been making me so grumpy in class.
* No class next Wednesday.
* Read 8-1 for Friday.
* Read 8-2 for Monday.
* HW: Due any time next Wedneday: 8-1, 8-2, and 8-3. 
    * You may have to read ahead a little if you want to start the 
      Skiena problems before Friday.
    * If you want implementation practice, you might think about how to
      implement Knapsack.

### Extra Credit

#### Academic

* CS Extras Thursday: Resume Reviews
* Saturday night movie/concert

#### Peer

* Jazz band tonight.
* Diwali Friday.
* Smash Bros tournament on Saturday.
* Translations this weekend.

### Questions

The Stamps problem
------------------

Input: Set of integers (1, 2, 7, 15, 25) + another integer (t)
Goal: Find the smallest set of integers whose sum = t.  You may 
      repeat any integer

Example: 14

* Bad answer 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 
* Best answer 7 + 7

Five primary techniques for doing this kind of problem

* Divide and conquer
* Greed
* Exhaustive search
* Think a lot about it
* Turn the problem into a graph and solve some graph algorithm on that
  graph.

A greedy solution

    set = { }
    For v = largest to smallest
      while (v <= t)
        t -= v
        set += { v }
    If t == 0
      return set
    else
      Report that no solution is available

Example

    t = 23, values = 25, 15, 7, 2, 1
    t = 23, set = { }, v = 25   NO
    t = 23, set = { }, v = 15   YES
    t = 8, set = { 15 }, v = 15 NO
    t = 8, set = { 15 }, v = 7 YES
    t = 1, set = { 15, 7 }, v = 7 NO
    t = 1, set = { 15, 7 }, v = 2 NO
    t = 1, set = { 15, 7 }, v = 1 YES
    t = 0, set = { 15, 7, 1 }, v = 1 NO

But what about 21 and 37?
   
   21: 15, 2, 2, 2 (but 7, 7, 7 is better)
   37: 25, 7, 2, 2, 1 (but 15, 15, 7 is better)

Hack: If (v + next-smallest) <= t

Counter-Example: 1, 20, 25, 50.  Make 80.

Hacking at the greedy algorithm is unlikely to succeed.

Divide-and-conquer is likely to be wrong.

Exhaustive search v1

    For i = 1 to t
      Make all sets of size i
      Determine if any of those sets sums to t.  
      If so, return that set

Exhaustive search v2

    minimize(values, t) => set
      if t == 0
        return { }
      otherwise
        tmp = universe; (a really big set)
        for each v in values
          tmp = minimize(values, t-v)
          if (sizeof(tmp)) < sizeof(best)
            best = tmp + { v }

Dynamic programming
-------------------

Usually used for optimization problems, particularly optimization
problems that have a simple but expensive recursive solution.

Two ideas:

* Use a table to keep track of already-computed results
    * How much does that help?
* Build the table from smallest to largest instead of largest to smallest
* The algorithm to build the table 

<pre class="programlisting">
    minimize(values, t) => set
      table = ....;
      for (i = 0; i <= t; i++)
        table[i] = universe; (a really big set)
        for each v in values
          if (table[t-v] < sizeof(best))
            best = table[t-v] + { v }
</pre>

The Knapsack problem
--------------------

Like the stamp problem:

Input is 

* a set of pairs (weight,worth)
* total weight

Goal: Find a subset of the pairs whose total weight <= total weight
whose worth is maximized

Harder: 

* Each element has a different "worth"
* Finite numbers of each element