Content

Knapsack Problem Defined Knapsack: Brute-Force Knapsack: Greedy Knapsack: Dynamic Programming Knapsack: Branch and Bound Shorest Path Algorithms <- Go Back

EECS 281: Data Structures and Algorithms

Section 20

Knapsack Shortest Path

University of Michigan at Ann Arbor

Last Edit Date: 06/15/2023

Disclaimer and Term of Use:

1. 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

2. 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.

3. This work is licensed under a Creative Commons Attribution 4.0 International License.

---

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

• Return maxVal, the maximum value the thief can carry in the knapsack

Variations 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

Knapsack: Brute-Force

• Generate possible solution space

  • Given an initial set of N items

  • Consider all possible subsets

• Filer feasiable solution set

  • Discard subsets with setSize > M

• Determine optimal solution

  • Find maxVal in feasible solution set

	1	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)$.

Knapsack: Greedy

Appraches:

• Steal highest vallue item first

  • Might not work if large items have high value

• Steal lowest size (weight) item 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

• 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

Knapsack: 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 Idenpendent Subset

• 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

    • Look at knapsacks from size 0 up to M

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

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

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 with greedy 0-1 Knapsack (by value density)

• 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

Shorest Path Algorithms

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

  • Ituition: 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 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)

© Sample Academy