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?

                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)

Sample call

(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)))

Improve call

(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)))

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))

(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))))))

The String Matching Problem