Warning! You are probably being recorded (and transcribed).
Approximate overview
When are the SEPC elections?
I don’t know. Ask an SEPC member.
How can we modify the stamps solution to extract the list of stamps?
fillTable(V, C)
table[0] = 0
for v in V
table[v] = 1
for c in 1:C
if (table[c] == infy)
table[c] = findMin(table, V, c)
// Return the smallest number of stamps needed to make c cents
findMin(table, V, c)
minSoFar = infinity
for v : V
if (v == c)
return 1
else if c-v > 0
if (table[c-v] < minSoFar)
minSoFar = table[c-v]
return 1 + minSoFar
stamps(V, C)
table = fillTable(V, C)
return table[C]
umfindMin, but we need it to return both
the number and the set of stamps.table (or something similar), we should update um.fillTable(V, C)
table = new array of integers of size (C+1)
um = new array of lists of size (C+1)
table[0] = 0
um[0] = { }
for v in V
table[v] = 1
um[v] = { v }
for c in 1:C
if (table[c] == infinity)
(num,stamps) = findMin(table, V, c)
table[c] = num
um[c] = stamps
// Return the smallest number of stamps needed to make c cents PLUS
// the set of stamps that makes that
findMin(table, V, c)
minSoFar = infinity
minoListSoFar = { }
for v : V
if (v == c)
return 1,{ v }
else if c-v > 0
if (table[c-v] < minSoFar)
minSoFar = 1 + table[c-v]
// QUESTION: WE UPDATE BECUAUSE table[c-v] HAS FEWER STAMPS
// THAN WE'VE SEEN SO FAR. WHAT DOES THAT MEAN ABOUT UPDATING
// minListSoFar?
minListSoFar = { v } + um[c-v]
return minSoFar,minListSoFar
stamps(V, C)
table = fillTable(V, C)
return um[C]
Consider a set of items, which we represent as \((v_i, w_i)\) pairs and a designated total weight, \(W\), that you can carry. Find a set of items whose total weight is less than or equal to \(W\) and that maximizes the total value.
Annoying rephrasing:
Given a set \(I = \{ (v_i, w_i) \} \subset N^+ \times N^+\) (representing value/weight pairs) and an integer \(W \in N^+\) (representing weight), find a set \(M = \{ (u_j, x_j) \} \subseteq I\) such that
Greed fails! E.g.,
(15, 15)
(14, 8)
(14, 8)
W = 16
Observation: In effect, we want our DP solution to try all the “reasonable” sets of items.
We are computing knapsack(I,W)
Two key issues for DP:
What is your recursive formulation?
I smaller? (I is a set of \((v_i, w_i)\) pairs.)
W smaller? (W is a non-negative integer.)
knapsack(I, W)
if (empty(I))
return 0
else if (W < 0)
return negative infinity
else
let i = (v,w) be an element of I
// heaviest, lightest, cheapest, expensiveist, ??
max (knapsack(I - { i }, W),
v + knapsack(I - { i }, W - w))
We’ll try this for our counter-example above
a = (15, 15)
b = (14, 8)
c = (14, 8)
I = { a, b, c}
W = 16
knapsack({ a, b, c}, 16)
max (knapsack({ b, c }, 16), // 28 (see below)
15 + knapsack({ b, c }, 1)
knapsack({ b, c }, 16)
max (knapsack({ c }, 16),
14 + knapsack({ c }, 8))
knapsack({ c }, 16)
max (knapsack({ }, 16)
14 + knapsack({ }, 8))
knapsack({ }, 16) = 0
knapsack({ }, 8) = 0
knapsack({ c }, 16)
max (0, 14 + 0) = 14
knapsack({ c }, 8)
max (knapsack({ }, 8)
14 + knapsack({ }, 0))
knapsack({ }, 0) = 0
knapsack({ c }, 8) = max(0, 14 + 0) = 14
knapsack({ b, c }, 16)
max (14, 14 + 14) = 28
knapsack({ b, c }, 1)
max (knapsack({ c }, 1),
14 + knapsack({ c }, -7))
// Note: When the remaining weight is negative, we skip the option
knapsack({ c }, 1)
// Weight of c is bigger than 1, so this is not valid
What table might support that recursive formulation? (What indices will our table have?)
Weight
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---
{}| | | | | | | |
S +---+---+---+---+---+---+---+---
U {i1}| | | | | | | |
B +---+---+---+---+---+---+---+---
S {i1,i2}| | | | | | | |
E +---+---+---+---+---+---+---+---
T {i1,i2,i3}| | | | | | | |
+---+---+---+---+---+---+---+---
{i1,i2,i3,i4}| | | | | | | |
+---+---+---+---+---+---+---+---
| | | | | | | |
i1 = (v1,w1), i2 = (v2, w2), i3 = (v3, w3), ...
The i's are items
Note that the last element of the set corresponds to the row of the set.
Assume $$n$$ rows and $$W$$ columns.
Algorithm
knapsack(I, W)
if (empty(I))
return 0
if W == 0
return 0
else
let i = (v,w) be an element of I
// heaviest, lightest, cheapest, expensiveist, ??
if (w <= W)
return max (knapsack(I - { i }, W), v + knapsack(I - { i }, W - w))
else
return knapsack(I - { i }, W)
knapsack(I, W) {
fillKnapsackTable(I, W)
return table(|I|, W)
}
fillKnapsackTable(I, W) {
// Initialization
for col = 0 to W
table[col, 0] = 0
for row = 0 to |I|
table[0, row] = 0
// Fill the rest of the table
for col = 1 to W
for row = 1 to |I|
// THINK ABOUT THIS FOR NEXT TIME!
}
Given two strings, \(S = s_1, s_2, ..., s_n\) and \(T = t_1, t_2, ... t_m\), find the longest possible matching substrings in \(S\) and \(T\), where a substring is a sequence of elements in order, but possibly with gaps.
An example
0 1 2 3 4 5 6 7 8
S a b x g r y i p n
T g r x p i y n o
Solution?
THINK ABOUT THE SOLUTION FOR NEXT TIME
THINK ABOUT HOW YOU MIGHT WRITE THE RECURSIVE FORMULATION FOR NEXT TIME
Observations?