Lecture 3 – Linked Lists
Lecture 24
Knapsack Solved All Ways
Shortest Path Algorithms
EECS 281: Data Structures & Algorithms
http://xkcd.com/287
Many
http://xkcd.com/287/
Data Structures & Algorithms
The Knapsack Problem
3
Knapsack Problem Defined
• A thief robbing a safe finds it filled with N
items
– Items have various sizes (or weights)
– Items have various values
• The thief has a knapsack of capacity M
• Problem: Find maximum value the thief
can pack into their knapsack that does not
exceed capacity M
4
• Assume a knapsack with capacity M = 11
• There are N = 5 different items
• Return maxVal, the maximum value the
thief can carry in the knapsack
Example: Knapsack
1 2 3 4 5
Size 1 2 5 6 7
Value 1 6 18 22 28
5
Variations on a Theme
• Each item is unique (the Standard)
– Known as the 0-1 Knapsack Problem
– Must take an item (1) or leave it behind (0)
• Finite amount of each item (explicit list)
• Infinite number of copies of each item
• Fractional amount of item can be taken
• Using weight (wi) instead of size
6
Solve Knapsack Problem
Using multiple algorithmic approaches
• Brute-Force
• Greedy
• Divide and Conquer
• Dynamic Programming
• Backtracking
• Branch and Bound
Data Structures & Algorithms
The Knapsack Problem
Data Structures & Algorithms
Knapsack: Brute-Force
9
Knapsack: Brute-Force
• Generate possible solution space
– Given an initial set of N items
– Consider all possible subsets
• Filter feasible solution set
– Discard subsets with setSize > M
• Determine optimal solution
– Find maxVal in feasible solution set
Brute-Force
Knapsack:
1 2 3 4 5 Val
0 0 0 0 0 0
1 0 0 0 0 1
0 1 0 0 0 6
1 1 0 0 0 7
0 0 1 0 0 18
1 0 1 0 0 19
1 1 1 0 0 25
0 0 0 1 0 22
1 0 0 1 0 23
0 1 0 1 0 28
1 1 0 1 0 29
0 0 1 1 0 40
1 0 1 1 0 41
0 1 1 1 0 46
1 1 1 1 0 47
10
1 2 3 4 5 Val
0 0 0 0 1 28
1 0 0 0 1 29
0 1 0 0 1 34
1 1 0 0 1 35
0 0 1 0 1 46
1 0 1 0 1 47
1 1 1 0 1 53
0 0 0 1 1 50
1 0 0 1 1 51
0 1 0 1 1 56
1 1 0 1 1 57
0 0 1 1 1 68
1 0 1 1 1 69
0 1 1 1 1 74
1 1 1 1 1 75
1 2 3 4 5
Size 1 2 5 6 7
Value 1 6 18 22 28
11
Brute-Force Pseudocode
1 bool array possSet[1..N] (0:leave,1:take)
2 maxVal = 0
3 for i = 1 to 2N
4 possSet[] = genNextPower(N)
5 setSize = findSize(possSet[])
6 setValue = findValue(possSet[])
7 if setSize <= M and setValue > maxVal
8 bestSet[] = possSet[]
9 maxVal = setValue
10 return maxVal
12
Brute-Force Efficiency
• Generate possible solution space
– Given an initial set of N items
– Consider all possible subsets
– O(2N)
• Filter feasible solution set
– Discard subsets with setSize > M
– O(N)
• Determine optimal solution
– Find maxVal in feasible solution set
– O(N)
O(N2N)
Data Structures & Algorithms
Knapsack: Brute-Force
Data Structures & Algorithms
Knapsack: Greedy
15
Greedy Approach
Approaches
• Steal highest value items first
– Might not work if large items have high value
• Steal lowest size (weight) items first
– Might not work if small items have low value
• Steal highest value density items first
– Might not work if large items have high value density
If greedy is not optimal, why not?
16
Example: Greedy Knapsack
• Assume a knapsack with capacity M = 11
• There are N different items, where
– Items have various sizes
– Items have various values
1 2 3 4 5
Size 1 2 5 6 7
Value 1 6 18 22 28
Ratio 1 3 3.6 3.67 4
17
Greedy Pseudocode
Input: integers capacity M, size[1..N], val[1..N]
Output: integer max value size M knapsack can carry
1 maxVal = 0, currentSize = 0
2 ratio[] = buildRatio(value[], size[])
3 // Sort all three arrays by ratio
4 sortRatio(ratio[], value[], size[])
5 for i = 1 to N //sorted by ratio
6 if size[i] + currSize <= M
7 currSize = currSize + size[i]
8 maxVal = maxVal + value[i]
9
10 return maxVal
18
Greedy Efficiency
• Sort items by ratio of value to size
– O(N log N)
• Choose item with highest ratio first
– O(N)
O(N log N) + O(N) O(N log N)
19
Fractional Knapsack: Greedy
• Suppose that thief can steal a portion of
an item
• What happens if we apply a Greedy
strategy?
• Is it optimal?
Data Structures & Algorithms
Knapsack: Greedy
Data Structures & Algorithms
Knapsack: Dynamic Programming
22
Dynamic Programming
• Enumeration with DP
– Examples: Fibonacci, Binomial Coefficient,
Knight Moves
– These are constraint satisfaction problems
• Optimization with DP
– Examples: Knapsack, Longest Increasing
Subsequence, Weighted Independent Subset
• Both can be solved top-down or bottom-up,
optimizations often favor bottom-up
23
DP Knapsack Approach
• A master thief prepares job for apprentice
– Alarm code, safe combination, and knapsack
– List of items in safe
– Table of items to put in knapsacks, 0 < x ≤ M
• Apprentice finds one extra item in safe
– Take it or leave it?
– Remove just enough to fit the new item
• Q: What should be removed?
• Q: When should the new item be included?
24
DP Knapsack Generalization
• Each item will either be taken or left
behind
– If it is too large it is left behind
– If room can be made to include it, it will be
taken only when it improves the haul
• Bottom-Up uses two nested loops
– Look at items one a time
• Look at knapsacks from size 0 up to M
– Build and use a 2D memo
25
1 2 3 4 5
Size 1 2 5 6 7
Value 1 6 18 22 28
0 1 2 3 4 5 6 7 8 9 10 11
0
1
2
3
4
5
Safe
Knapsack Size
S
a
fe
I
te
m
# 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1
0 1 6 7 7 7 7 7 7 7 7 7
0 1 6 7 7 18 19 24 25 25 25 25
0 1 6 7 7 18 22 24 28 29 29 40
0 1 6 7 7 18 22 28 29 34 35 40
27
Dynamic Programming: Knapsack
1 uint32_t knapsackDP(const vector
2 const size_t n = items.size();
3 vector
4 memo(n + 1, vector
5
6 for (size_t i = 0; i < n; ++i) {
7 for (size_t j = 0; j < m + 1; ++j) { // +1 for memo[][m]
8 if (j < items[i].size)
9 memo[i + 1][j] = memo[i][j];
10 else
11 memo[i + 1][j] = max(memo[i][j],
12 memo[i][j – items[i].size] + items[i].value);
13 } // for j
14 } // for i
15 return memo[n][m];
16 } // knapsackDP()
Run time is O(MN)
28
Reconstructing the Solution
• Included items improve a smaller solution,
excluded items do not
• If a smaller solution plus an item is greater
than or equal to a full solution without the
item it is included, otherwise it is excluded
• Use completed memo to determine the
items taken
• Work backward from (n, m) to (0, 0)
29
1 2 3 4 5
Size 1 2 5 6 7
Value 1 6 18 22 28
0 1 2 3 4 5 6 7 8 9 10 11
0
1
2
3
4
5
Safe
Knapsack Size
S
a
fe
I
te
m
# 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1
0 1 6 7 7 7 7 7 7 7 7 7
0 1 6 7 7 18 19 24 25 25 25 25
0 1 6 7 7 18 22 24 28 29 29 40
0 1 6 7 7 18 22 28 29 34 35 40
0
0
0
18
40
40
30
Knapsack DP Reconstruction
18 vector
19 const vector
20 const size_t n = items.size();
21 size_t c = m; // current capacity
22 vector
23
24 for (int i = n – 1; i >= 0; –i) { // use int for -1 loop exit
25 if (items[i].size <= c) { 26 if (memo[i][c - items[i].size] + items[i].value >= memo[i][c]) {
27 taken[i] = true;
28 c -= items[i].size;
29 } // if ..item added
30 } // if ..item fits
31 } // for i..0
32 return taken;
33 } // knapDPReconstruct()
Run time is O(N)
Data Structures & Algorithms
Knapsack: Dynamic Programming
Data Structures & Algorithms
Knapsack: Branch and Bound
33
Knapsack Branch and Bound
• The Knapsack Problem is an optimization
problem
• Branch and Bound can be used to solve
optimization problems
– Knapsack is a maximization
– Initial estimate and current best solution are a
“lower bound”
– Calculate partial solution, remainder is an
“upper bound” estimate
34
Knapsack B&B Elements
• promising(): total weight of items < M • solution(): any collection that is promising • lower_bound: starts with highest possible underestimate, ends with maximum value taken – Can start w/ Greedy 0-1 Knapsack (by value density) • upper_bound: sum of value of included items, plus an ”overestimate” of value that can fit in remaining space – Prune if upper_bound < lower_bound – Can use Greedy Fractional Knapsack • Don’t need permutations only combinations Data Structures & Algorithms Knapsack: Branch and Bound EECS 281: Data Structures & Algorithms Shortest Path Algorithms Data Structures & Algorithms Dijkstra’s Algorithm 39 Shortest Path Examples • Highway system – Distance – Travel time – Number of stoplights – Krispy Kreme locations • Network of airports – Travel time – Fares – Actual distance 40 Weighted Path Length • Consider an edge-weighted graph G = (V, E). • Let C(vi, vj) be the weight on the edge connecting vi to vj. • A path in G is a non-empty sequence of vertices P = {v1, v2, v3, …, vk}. • The weighted path length is given by C(vi, vi+1) i=1 k-1 41 The Shortest Path Problem Given an edge-weighted graph G = (V, E) and two vertices, vs V and vd V, find the path that starts at vs and ends at vd that has the smallest weighted path length 42 Single-Source Shortest Path • Given an edge-weighted graph G = (V, E) and a vertex, vs V, find the shortest path from vs to every other vertex in V • To find the shortest path from vs to vd, we must find the shortest path from vs to all other vertexes in G 43 The shortest weighted path from b to f: {b, a, c, e, f} a b c d e f 3 5 1 5 1 54 2 44 a b c d e f 3 5 1 5 1 54 2 The shortest weighted path from b to f: {b, a, c, e, f} A shortest unweighted path from b to f: {b, c, e, f} 45 Shortest path problem undefined for graphs with negative-cost cycles {d, a, c, e, f} cost: 4 {d, a, c, d, a, c, e, f} cost: 2 {d, a, c, d, a, c, d, a, c, e, f} cost: 0 a b c d e f 3 5 1 5 -6 54 -8 46 Dijkstra’s Algorithm • Greedy algorithm for solving shortest path problem • Assume non-negative weights • Find shortest path from vs to every other vertex 47 Dijkstra’s Algorithm For each vertex v, need to know: • kv: Is the shortest path from vs to v known? (initially false for all v V) • dv: What is the length of the shortest path from vs to v? (initially for all v V, except vs = 0) • pv: What vertex precedes (is parent of) v on the shortest path from vs to v? (initially unknown for all v V) 48 v kv dv pv a F b F 0 c F d F e F f F Find shortest paths to b 3 5 1 5 1 54 2 a b c e f d 49 v kv dv pv a F 3 b b T 0 -- c F 5 b d F e F f F 3 5 1 5 1 54 2 a b c e f d 50 v kv dv pv a T 3 b b T 0 -- c F 4 a d F 8 a e F f F 3 5 1 5 1 54 2 a b c e f d 51 v kv dv pv a T 3 b b T 0 -- c T 4 a d F 6 c e F 8 c f F 3 5 1 5 1 54 2 a b c e f d 52 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e F 8 c f F 11 d 3 5 1 5 1 54 2 a b c e f d 53 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e T 8 c f F 9 e 3 5 1 5 1 54 2 a b c e f d 54 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e T 8 c f T 9 e 3 5 1 5 1 54 2 a b c e f d 55 v kv dv pv a T 3 b b T 0 -- c T 4 a d T 6 c e T 8 c f T 9 e 4 3 98 6 a b c e f d 56 Dijkstra Complexity • O(V2) for a simple nested loop implementation, a lot like Prim’s – Intuition: for each vertex, find the min using linear search • O(E log V) for sparse graphs, using heaps – E for considering every edge – log E = O(log V2) = O(log V) for finding the shortest edge in heap • CLRS 24.3 has a good explanation 57 Dijkstra’s Algorithm 1 Algorithm Dijsktra(G, s0) 2 //Initialize 3 n = |V| 4 create_table(n) //stores k,d,p 5 create_pq() //empty heap 6 table[s0].d = 0 7 insert_pq(0, s0) O( ) O( ) O( ) O( ) O( ) 1 V 1 1 1 58 Dijkstra’s Algorithm (cont.) 1 while (!pq.isempty) 2 v0 = getMin() //heap top() & pop() 3 if (!table[v0].k) //not known 4 table[v0].k = true 5 for each vi Adj[v0] 6 d = table[v0].d + distance(vi, v0) 7 if (d < table[vi].d) 8 table[vi].d = d 9 table[vi].p = v0 10 insert_pq(d, vi) 11 12 for each v G(V,E) 13 //build edge set in T 14 (v, table[v].p) T(V, E’) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) O( ) E log E 1 1 1 + E/V 1 1 1 1 log E V 1 Data Structures & Algorithms Dijkstra’s Algorithm 60 Exercise Find the shortest path from O to T kv dv pv O A B C D E F T 61 All-pairs shortest path problem • Given an edge-weighted graph G = (V, E), for each pair of vertices in V find the length of the shortest weighted path between the two vertices Solution 1: Run Dijkstra V times Other solutions: Use Floyd’s Algorithm (dense graphs) Use Johnson’s Algorithm (sparse graphs) 62 NOTE! • We usually end up stopping here for lecture material • You don’t need to know Floyd-Warshall for the exam, but it seems a shame to delete perfectly good slides • If you ever need it for a reference, you’ve got it! 63 Solution 2: Floyd’s Algorithm • Floyd-Warshall Algorithm • Dynamic programming method for solving all-pairs shortest path problem on a dense graph • Uses an adjacency matrix • O(V3) (best, worst, average) 64 Weighted path length • Consider an edge-weighted graph G = (V,E), where C(v,w) is the weight on the edge (v,w). • Vertices numbered from 1 to |V| (i.e. V = {v1, v2, v3, …, v|V|}) 65 Weighted path length • Consider the set Vk = {v1, v2, v3, …, vk} for 0 ≤ k ≤ |V| • Pk(i,j) is the shortest path from i to j that passes only through vertices in Vk if such a path exists • Dk(i,j) is the length of Pk(i,j) Dk(i,j) = |Pk(i,j)| if Pk(i,j) exists otherwise { 66 Suppose k = 0 • V0 = Ø, so P0 paths are the edges in G: • Therefore D0 path lengths are: P0(i,j) = {i,j} if (i,j) E undefined otherwise { D0(i,j) = { |C(i,j)| if (i,j) E otherwise 67 a b c d e f 3 5 1 5 1 54 2 D0 a b c d e f a 1 b 3 5 c 2 4 d 5 5 e 1 f to fr o m 68 Floyd’s Algorithm • Add vertices to Vk one at a time • For each new vertex vk, consider whether it improves each possible path – Compute Dk(i,j) for each i,j in V – Minimum of: • Dk-1(i,j) • Dk-1(i,k) + Dk-1(k,j) 69 fr o m to D0 a b c d e f a 1 b 3 5 c 2 4 d 5 5 e 1 f D1 a b c d e f a 1 b 3 4 c 2 4 d 5 6 5 e 1 f Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) V1 = {a} 70 fr o m to D1 a b c d e f a 1 b 3 4 c 2 4 d 5 6 5 e 1 f D2 a b c d e f a 1 b 3 4 c 2 4 d 5 6 5 e 1 f V2 = {a, b} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 71 fr o m to D2 a b c d e f a 1 b 3 4 c 2 4 d 5 6 5 e 1 f D3 a b c d e f a 1 3 5 b 3 4 6 8 c 2 4 d 5 6 10 5 e 1 f V3 = {a, b, c} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 72 fr o m to D3 a b c d e f a 1 3 5 b 3 4 6 8 c 2 4 d 5 6 10 5 e 1 f D4 a b c d e f a 1 3 5 8 b 3 4 6 8 11 c 7 2 4 7 d 5 6 10 5 e 1 f V4 = {a, b, c, d} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 73 fr o m to D4 a b c d e f a 1 3 5 8 b 3 4 6 8 11 c 7 2 4 7 d 5 6 10 5 e 1 f D5 a b c d e f a 1 3 5 6 b 3 4 6 8 9 c 7 2 4 5 d 5 6 10 5 e 1 f V5 = {a, b, c, d, e} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 74 fr o m to D5 a b c d e f a 1 3 5 8 b 3 4 6 8 11 c 7 2 4 7 d 5 6 10 5 e 1 f D6 a b c d e f a 1 3 5 6 b 3 4 6 8 9 c 7 2 4 5 d 5 6 10 5 e 1 f V6 = {a, b, c, d, e, f} Dk(i,j) = min(Dk-1(i,j), Dk-1(i,k) + Dk-1(k,j)) 75 Floyd’s Algorithm 1 Floyd(G) { 2 // Initialize 3 n = |V|; 4 for (k = 0; k <= n; k++) 5 for (i = 0; i < n; i++) 6 for (j = 0; j < n; j++) 7 d[k][i][j] = infinity; 8 9 for (all (v,w) E) 10 d[0][v][w] = C(v,w) O( ) O( ) O( ) 76 Floyd’s Algorithm 11 // Compute next distance matrix 12 for (k = 1; k <= n; k++) 13 for (i = 0; i < n; i++) 14 for (j = 0; j < n; j++) 15 d[k][i][j] = min(d[k-1][i][j], 16 d[k-1][i][k] + d[k-1][k][j]); 17 } O( ) 77 What About the Paths? • Can’t simply reconstruct them at end • Add initialization: 1 for (i = 0; i < n; i++) 2 for (j = 0; j < n; j++) 3 // If edge doesn’t exist, no path 4 if (C(i,j) == infinity) 5 p[0][i][j] = NIL; 6 else 7 p[0][i][j] = j; 78 Updating Paths • When going through the triple-nested loop of the algorithm, if you ever update a weight, you must also update the path • See code next page 79 fr o m to P0 a b c d e f a - - c - - - b a - c - - - c - - - d e - d a - - - - f e - - - - - f f - - - - - - P1 a b c d e f a - - c - - - b a - a - - - c - - - d e - d a - a - - f e - - - - - f f - - - - - - V1 = {a} 80 Paths: Primary Loops 1 for (k = 1; k < n; k++) 2 for (i = 0; i < n; i++) 3 for (j = 0; j < n; j++) 4 // Compute next distance matrix 5 d[k][i][j] = min(d[k-1][i][j], 6 d[k-1][i][k] + d[k-1][k][j]); 7 // Compute next paths matrix 8 if (d[k-1][i][j] 9 <= d[k-1][i][k] + d[k-1][k][j]) 10 p[k][i][j] = p[k-1][i][j]; 11 else 12 p[k][i][j] = p[k-1][k][j]; O( ) O( ) 81 Worst Case Running Time • Add vertices to Vk one at a time – Outer loop executes |V| times • For each new vertex, consider whether it improves each possible path – Inner loops execute |V|2 times • Overall O(|V|3) • Better than running Dijkstra |V| times?