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

    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 }

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