Content
Knapsack Problem Defined Knapsack: Brute-Force Knapsack: Greedy Knapsack: Dynamic Programming Knapsack: Branch and Bound Shorest Path Algorithms <- Go BackUniversity of Michigan at Ann Arbor
Last Edit Date: 06/15/2023
Disclaimer and Term of Use:
We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file
This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.
This work is licensed under a Creative Commons Attribution 4.0 International License.
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 kanpsack of capacity M
Problem: Find maximum value the thief can pack into their knapsack that does not exceed capacity M
Example: Knapsack
Assume a knapsack with capacity M = 11
There are N = 5 different items
1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
Size | 1 | 2 | 5 | 6 | 7 |
Value | 1 | 6 | 18 | 22 | 28 |
maxVal
, the maximum value the thief can carry in the knapsackVariations on a Theme
Each item is unique (the stadrad)
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 ($w_i$) instead of size
Solve Knapsack Problem
Using multiple algorithm approaches
Brute-Force
Greedy
Dynamic Programming
Branch and Bound
Generate possible solution space
Given an initial set of N items
Consider all possible subsets
Filer feasiable solution set
Determine optimal solution
maxVal
in feasible solution set1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|
Size | 1 | 2 | 5 | 6 | 7 |
Value | 1 | 6 | 18 | 22 | 28 |
Brute-Force Pseudocode
bool array possSet[1 .. N] (0:leave, 1:take)
maxVal = 0
for i = 1 to 2^N
possSet[] = genNextPower(N)
setSize = findSize(possSet[])
setValue = findValue(possSet[])
if setSize <= M and setValue > maxVal
bestSet[] = possSet[]
maxVal = setValue
return maxVal
Brute-Force Efficiency
Generate possible solution space
Given an initial set of N items
Consider all possible subsets
$O(2^N)$
Filter feasible solution set
Discard subsets with setSize > M
$O(N)$
Determine optimal solution
Find maxVal
in feasible solution set
$O(N)$
As a result, the total time complexity for brute-force in knapsack problem is $O(N2^N)$.
Appraches:
Steal highest vallue item first
Steal lowest size (weight) item first
Steal highest value density items first
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 |
(1) Look for max value:
Items 5, 2, and 1. The total value is 28 + 6 + 1 = 35
(2) Look for min size:
Items 1, 2, and 3. The total value is 1 + 6 + 18 = 25
(3) Look for max ratio:
Items 5, 2 and 1. The total value is 28 + 6 + 1 = 35
None of the above finds the optimal solution, which should be 40.
Greedy Pseudocode
Input: integers capacity M
, size[1..N]
, val[1..N]
Output: integers max value size M knpsack can carry
maxVal = 0, currentSize = 0
ratio[] = buildRatio(value[], size[])
// Sort all three arrays by ratio
sortRatio(ratio[], value[], size[])
for i = 1 to N // sorted by ratio
if size[i] + currSize <= M
currSize = currSize + size[i]
maxVal = maxVal + value[i]
return maxVal
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) \Rightarrow O(N \log N)$
Fractional Knapsack Greeday
Suppose that thief can steal a portion of an item
If we look at the ratio, we can get the optimal solution
Enumeration with DP
Examples: Fibonacci, Binomial Coefficient, Knight Moves
These are constraint satisfaction problems
Optimization with DP
Both can be solved top-down or bottom-up, optimizations often favor bottom-up
DP Kanpsack 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 \le M$
Apprentice finds one extra item in safe
Take it or leave it?
Remove just enough to fit the new item
Ouestion: What should be removed?
Question: When should the new item be included?
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
Build and use a 2D memo
Dynamic Programming: Knapsack
1 uint32_t knapsackDP(const vector<Item> &items, const size_t m) {
2 const size_t n = items.size();
3 vector<vector<uint32_t>>
4 memo(n + 1, vector<uint32_t>(m + 1, 0)); // +1, +1
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()
The run time is $O(MN)$.
Reconstructing the Solution
Include items improve a smaller solution, exclude 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)
1 vector<bool> knapDPReconstruct(const vector<Item>& items,
2 const vector<vector<uint32_t>>& memo, const size_t m) {
3 const size_t n = items.size();
4 size_t c = m;
5 vector<bool> taken(n, false);
6
7 for (int i = n - 1; i >= 0; i--) {
8 if (items[i].szie <= c) {
9 if (memo[i][c - items[i].size] + items[i].value >= memo[i][c]) {
10 taken[i] = true;
11 c -= items[i].szie;
12 }
13 }
14 }
15 return taken;
16 }
Run time is $O(N)$
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
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
upper_bound
: sum of value of included items, plus an "overestimate" of value thtat can fit in remaining space
Prune if upper_bound < lower_bound
Can use Greedy Fractional Knapsack
Do not need permutations only combinations
Shortest Path Examples:
Highway system
Distance
Travel time
Number of stoplights
Krispy Kreme locations
Network of airports
Travel time
Fares
Actual distance
Weighted Path Length
Consider an edge-weighted graph G = (V, E)
Let $C(v_i, v_j)$ be the weight on the edge connecting $v_i$ to $v_j$
A path in G is a non-empty sequence of vertices $P = \{v_1, v_2, v_3,...,v_k\}$
The weighted path length is given by $\sum_{i=1}^{k-1}C(v_i, v_{i + 1})$
The Shorest Path Problem
Given an edge-weighted graph $G=(V, E)$ and two vertices, $v_s \in V$ and $v_d \in V$, find the path that starts at $v_s$ and ends $v_d$ that has the smallest weighted path length
Single-Source Shorest Path
Given an edge-weighted graph $G=(V, E)$ and a vertex, $v_s \in V$, find the shorest path from $v_s$ to every other vertex in $V$
To find the shorest path from $v_s$ to $v_d$, we must find the shorest path from $v_s$ to all other vertices in $G$
i. Dijkstra's Algorithm
Greedy algorithm for solving shotest path problem
Assume non-negative weights
Find shorest path from $v_s$ to every other vertex
For each vertex $v$, need to know:
$k_v$: Is the shortest path from $v_s$ to $v$ known? (initially false for all $v \in V$)
$d_v$: What is the length of the shorest path from $v_s$ to $v$? (initially $\infty$ for all $v \in V$, except $v_s = 0$)
$p_v$: What vertex precefes (is parent of) $v$ on the shorest path from $v_s$ to $v$? (initially unknown for all $v \in V$)
Dijkstra Complexity
$O(V^2)$ for a simple nested loop implementation, a lot like Prim's
$O(E \log V)$ for sparse graphs, using heaps
E for considering every edge
$\log E = O(\log V^2) = O(\log V)$ for finding the shorest edge in heap
Pseudocode
1 Algorithm Dijsktra(G, s0)
2 //Initialize
3 n = |V| // O(1)
4 create_table(n) //stores k,d,p // O(V)
5 create_pq() //empty heap // O(1)
6 table[s0].d = 0 // O(1)
7 insert_pq(0, s0) // O(1)
1 while (!pq.isempty) // O(E)
2 v0 = getMin() //heap top() & pop() // O(log E)
3 if (!table[v0].k) //not known // O(1)
4 table[v0].k = true // O(1)
5 for each vi $\in$ Adj[v0] // O(1 + E / V)
6 d = table[v0].d + distance(vi, v0) // O(1)
7 if (d < table[vi].d) // O(1)
8 table[vi].d = d // O(1)
9 table[vi].p = v0 // O(1)
10 insert_pq(d, vi) // O(log E)
11
12 for each v $\in$ G(V,E) // O(V)
13 //build edge set in T
14 (v, table[v].p) $\in$ T(V, E’) // O(1)