CSC301.01 2015F, Class 34: Dynamic Programming (2)
==================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* A DP Solution to the Stamps Problem.
* The Knapsack Problem.
* The String Matching Problem.

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

### Admin

* Handout!  Code for DP solution.
* No class next Wednesday.
* Friday PSA.

### Upcoming Work

* Read 8-3 and 8-4 for Monday.
* HW: Due any time next Wedneday: 8-1, 8-2, and 8-3. 

### Extra Credit

#### Academic

* Saturday night movie/concert
* Translations is now sold out.

#### Peer

* Diwali Friday.
* Smash Brothers Tournament Saturday.
* Metal Radio tonight.
* Local Foods Thanksgiving.
* Swim meet Saturday.

### No Extra Credit, But Good

* Contra Dance tonight
* Concert tonight

### Questions

A DP Solution to the Stamps Problem
-----------------------------------

* Demo.  Look, you can read boring repetitive text!
* Implementation note: We need nested loops.
    * Outer loop: For each value from 1 to the goal value (iterator
      called `pos`.
    * Inner loop: For each stamp value (iterator called `val`)

The Knapsack Problem
--------------------

How do we modify that code to achieve a solution to the knapsack problem?

<pre>
                Stamps                  Knapsack
                ------                  --------
Input 1         total price             total weight

Input 2         list of stamp costs     list of weight/value pairs

Output          list of stamps          list of weight/value pairs

Restrictions    (sum lst) = price       (sum weights) <= total weight
                Stamps can appear       Each pair can appear at most once
                  multiple times

Goal            Minimize (length lst)   Maximize (sum values)
</pre>

Sample call

<pre>
(knapsack 100 (list (vector "cat1" 8 1) (vector "cat2" 9 1)
                    (vector "kitten1" 2 1) (vector "kitten2" 2 1)
                    (vector "ukitten1" 1 1) (vector "ukitten2" 1 1)
                    (vector "dog" 35 100) (vector "lizard" 40 20)
                    (vector "mm" 120 300)))
</pre>

Improve call

<pre>
(knapsack 37 (list (vector "knife" 1 3) (vector "knife" 1 2)
                   (vector "knife" 1 2) (vector "knife" 1 1)
                   (vector "knife" 1 1) (vector "knife" 1 1)
                   (vector "flashlight" 2 5) (vector "flashlight" 2 3)
                   (vector "flashlight" 2 1) (vector "flashlight" 2 1)
                   (vector "blanket" 7 10) (vector "extra blanket" 7 5)
                   (vector "another blanket" 7 1)
                   (vector "tent" 15 20) (vector "spare tent" 15 6)
                   (vector "complete-kamping-kit" 25 25)))
</pre>

What changes should we make to the algorithm as stated?  (Either Scheme
code or conceptially?)

* Instead of doing "for each value" in the inner loop, we should do
  "for each item"
* Instead of subtracting the value from the current value, substract  
  the weight from the goal weight.
* In looking at the previous entry in the table, you must also check
  whether the item has been used in that entry.  (If so, that entry
  isn't likely to be helpful.)
    * Problem: There may be multiple ways to make one weight
    * Do you generate them all?
    * Do you cross your fingers and hope that it doesn't matter and
      you can just use one of them? [STARTING POINT]
    * Do you find a counter-example?
    * Do you do a formal proof that it doesn't matter and you can use
      just one of them?
    * Do you do an informal proof that it doesn't matter and you can use
      just one of them?
* Instead of the guess with the least number of entries, we pick the guess
  with the maximum value.
* It might be that the value we get for the previous weight is higher
  `(list (vector "thing1" 15 10) (vector "thing2" 15 10) 
         (vector "catinthehat" 29 40))`

<pre class="programlisting">
(define knapsack
  (lambda (limit things)
    (let ([table (make-vector (+ limit 1) #f)])
      (vector-set! table 0 (cons 0 null))
      (let loop ([pos 1])
        (when (<= pos limit)
          (log)
          (log "Finding the optimal value for" pos)
          (let kernel ([guess (vector-ref table (- pos 1)] ; A starting point
                       [lst thing])
            (cond
              [(null? lst)
               (log "The optimal value for" pos "is" guess)
               (vector-set! table pos guess)
               (loop (+ pos 1))]
              [else
               (let* ([val (car lst)]
                      [remainder (- pos (weight val)])
                 (log "Trying item" (car lst))
                      " giving us a remainder of" remainder)
                 (cond
                   [(negative? remainder)
                    (log "  Negative remainder.  Item too heavy!")
                    (kernel guess (cdr lst))]
                   [else
                    (let ([alternate (vector-ref table remainder)])
                      (log "  Best option for" remainder "is" (cdr alternate) 
                           "which has value" (car alternate))
                      (cond
                        [(and (> (+ (worth val) (car alternate)) (car guess))
                              (...))
                         (let ([newguess (cons (+ 1 (car alternate))
                                               (cons val (cdr alternate)))])
                           (log "  Updating best guess to" (cdr newguess)
                                "which is" (car newguess) "stamps")
                           (kernel newguess (cdr lst)))]
                        [else
                         (log "  Retaining prior guess")
                         (kernel guess (cdr lst))]))]))]))))
        (let ([answer (vector-ref table value)])
           (if answer
               (cdr answer)
               (error "It is not possible to make a value of" value))))))
</pre>

The String Matching Problem
---------------------------