Skip to main content

Classic problems

By Afshine Amidi and Shervine Amidi

Traveling salesman

Given nn cities c1,...,cnc_1, ..., c_n, the traveling salesman problem (TSP) is a classic problem that aims at finding the shortest path that visits all cities exactly once and then returns to the starting city.

The distance between each pair of cities (ci,cj)(c_i, c_j) is noted di,jd_{i,j} and is known.

A naive approach would consist of enumerating all possible solutions and finding the one that has the minimum cumulative distance. Given a starting city, there are (n1)!(n-1)! possible paths, so this algorithm would take O(n!)\mathcal{O}(n!) time. This approach is impracticable even for small values of nn.

Luckily, the Held-Karp algorithm provides a bottom-up dynamic programming approach that has a time complexity of O(n22n)\mathcal{O}(n^22^n) and a space complexity of O(n2n)\mathcal{O}(n2^n).

Suppose c1c_1 is the starting city. This arbitrary choice does not influence the final result since the resulting path is a cycle. We define the following quantities:

  • Ck\mathscr{C}_k contains all sets of kk distinct cities in {c2,...,cn}\{c_2, ..., c_n\}:
    for k[ ⁣[0,n1] ⁣],Ck={CkCk{c2,...,cn},#Ck=k}\textrm{for }k\in[\![0, n-1]\!],\quad\quad\mathscr{C}_k=\Big\{C_k | C_k\subseteq\{c_2, ..., c_n\}, \#C_k=k\Big\}
    We note that Ck\mathscr{C}_k has a size of (n1k)\displaystyle\binom{n-1}{k}.
  • g(Ck,cj)g(C_k, c_j) is the distance of the shortest path that starts from c1c_1, goes through each city in CkCkC_k\in\mathscr{C}_k exactly once and ends at cjCkc_j\notin C_k.

The solution is found iteratively:

  • Initialization: The shortest path between the starting city c1c_1 and each of the other cities cjc_j with no intermediary city is directly given by d1,jd_{1, j}:

    j[ ⁣[2,n] ⁣],g(C0,cj)=d1,j\forall j\in[\![2, n]\!], \quad\boxed{g(C_0, c_j) = d_{1, j}}

  • Compute step: Suppose that for all Ck1Ck1C_{k-1}\in\mathscr{C}_{k-1} and ci∉Ck1c_i\not\in C_{k-1}, we know the distance of the shortest path g(Ck1,ci)g(C_{k-1}, c_i) between c1c_1 and cic_i via the k1k-1 cities in Ck1C_{k-1}.

    Let's take CkCkC_k\in\mathscr{C}_k. For all ciCkc_i\in C_k, we note that Ck\{ci}Ck1C_k\backslash\{c_i\}\in\mathscr{C}_{k-1} and that (naturally) ci∉Ck\{ci}c_i\not\in C_k\backslash\{c_i\}, which means that g(Ck\{ci},ci)g(C_k\backslash\{c_i\}, c_i) is known.

    We can deduce the distance of the shortest path between c1c_1 and cj∉Ckc_j\not\in C_k via kk cities by taking the minimum value over all second-to-last cities ciCkc_i\in C_k:

    CkCk,cjCk,g(Ck,cj)=minciCk{g(Ck\{ci},ci)+di,j}\forall C_k\in\mathscr{C}_k, \forall c_j\notin C_k,\quad\boxed{g(C_k, c_j) = \underset{c_i\in C_k}{\textrm{min}}\Big\{g(C_k\backslash\{c_i\}, c_i)+d_{i, j}\Big\}}

    Each step kk has the following complexities:

    k×(n1k)×(n1k)\displaystyle k\times(n-1-k)\times\binom{n-1}{k}(n1k)×(n1k)\displaystyle(n-1-k)\times\binom{n-1}{k}
  • Final step: The solution is given by g({c2,...,cn},c1)g(\{c_2, ..., c_{n}\}, c_1).

    Since Cn1={c2,...,cn}C_{n-1}=\{c_2, ..., c_{n}\}, the last step of the algorithm gives:

    g(Cn1,c1)=mini[ ⁣[2,n] ⁣]{g(Cn1\{ci},ci)+di,1}\boxed{g(C_{n-1}, c_1)=\underset{i\in[\![2, n]\!]}{\textrm{min}}\Big\{g(C_{n-1}\backslash\{c_i\}, c_i)+d_{i,1}\Big\}}


The 0/1 knapsack problem is a classic problem where the goal is to maximize the sum of values of items put in a bag that has a weight limit. Here, "0/1" means that for each item, we want to know whether we should include it (1) or not (0).

More formally, we have a bag of capacity CC and nn items where each item i[ ⁣[1,n] ⁣]i\in[\![1, n]\!] has value viv_i and weight wiw_i. We want to find a subset of items I{1,...,n}\mathscr{I}\subseteq\{1, ..., n\} such that:

I=argmaxI[ ⁣[1,n] ⁣]iIvi with iIwiC\boxed{\mathscr{I}=\underset{I\subseteq[\![1, n]\!]}{\textrm{argmax}}\sum_{i\in I}v_i}\quad\textrm{ with }\sum_{i\in\mathscr{I}}w_i \leqslant C

A naive approach would consist of trying out every combination of the nn items and take the one with the maximum value which also satisfies the cumulative weight constraint. Such an approach has a time complexity of O(2n)\mathcal{O}(2^n).

Luckily, this problem can be solved with a bottom-up dynamic programming approach that has a time complexity of O(nC)\mathcal{O}(nC) and a space complexity of O(nC)\mathcal{O}(nC).

We note Vi,jV_{i, j} the maximum value of a bag of capacity j[ ⁣[0,C] ⁣]j\in[\![0, C]\!] that contains items among {1,2,...,i}\{1, 2, ..., i\}. Our objective is to get Vn,CV_{n, C}.

  • Initialization: The maximum values of the following bags are known:

    • Bags of capacity 0: Vi,0=0V_{i, 0}=0.

    • Bags with 0 item: V0,j=0V_{0, j}=0.

  • Compute maximum value: Starting from i=1i=1 and j=1j=1, we iteratively fill the 2D array of maximum values from left to right, top to bottom.

    In order to determine the maximum value Vi,jV_{i, j} of a bag of capacity jj containing items among {1,...,i}\{1, ..., i\}, we need to choose between two hypothetical bags:

    • Bag 1: contains item ii. VB1V_{B_1} is found by adding the value viv_i of item ii to the maximum value of the bag of capacity jwij-w_i containing items among {1,...,i1}\{1, ..., i-1\}.

      VB1=Vi1,jwi+vi\boxed{V_{B_1}=V_{i-1, j-w_i} + v_i}

    • Bag 2: does not contain item ii. VB2V_{B_2} is already known: it is the maximum value of the bag of capacity jj containing items among {1,...,i1}\{1, ..., i-1\}.

      VB2=Vi1,j\boxed{V_{B_2}=V_{i-1, j}}

We choose the best potential bag:

Vi,j=max(VB1,VB2)\boxed{V_{i, j}= \max(V_{B_1}, V_{B_2})}

When the 2D array is filled, the desired value is Vn,CV_{n, C}.

  • Get final items: In order to know which items were selected, we start from position (i,j)=(n,C)(i, j)=(n, C) of the 2D array and traverse it iteratively:

    • Case Vi,jVi1,jV_{i, j}\neq V_{i-1, j}: This means that item ii was included. We go to position (i1,jwi)(i-1, j-w_i) and include item ii in the set of included items.

    • Case Vi,j=Vi1,jV_{i, j} = V_{i-1, j}: This means that item ii was not included. We go to position (i1,j)(i-1, j).

      We repeat this process until retrieving all items.


Given a chessboard of size N×NN\times N, the NN-Queens problem aims at finding a configuration of NN queens such that no two queens attack each other.

A queen is a chess piece that can move horizontally, vertically or diagonally by any number of steps.

The solution can be found using a backtracking approach:

  • Step 1: Put the 1st1^{st} queen on the chessboard.

  • Step 2: Put the 2nd2^{nd} queen in the second column of the chessboard. As long as the partial configuration is invalid, keep changing its position until conditions are satisfied.

  • Step 3: If there is nowhere to place the next queen, go back one step and try the next partial configuration.

  • Step 4: Continue this process until finding a valid solution.

Coin change

Given an unlimited number of coins of values {c1,..,ck}\{c_1, .., c_k\}, the coin change problem aims at finding the minimum number of coins that sum up to a given amount SS. By convention, we assume that c1<...<ckc_1<...<c_k.

In other words, we want to find the minimum value of x=x1+...+xkx = x_1 + ... + x_k such that

S=i=1kxiciS = \sum_{i=1}^{k} x_i c_i

The bottom-up dynamic programming solution iteratively computes the minimum amount of coins dsd_s for each amount s{1,...,S}s\in\{1, ..., S\}.

This approach runs in O(S)\mathcal{O}(S) time and takes O(S)\mathcal{O}(S) space:

  • Initialization:

    • Initialize array D=[d0,...,dS]D=[d_0, ..., d_S] with zeros.

    • For each i[ ⁣[1,...,k] ⁣]i\in[\![1, ..., k]\!], set dcid_{c_i} to 11 since we already know that the corresponding amount only needs 1 coin.

  • Compute step: Starting from s=c1+1s=c_1+1, we iteratively fill array DD.

    In order to obtain amount ss, we distinguish two cases:

    • Case i,dsci>0\exists i, d_{s-c_i} > 0: We look back at valid values dscid_{s-c_i} and see which coin cic_i minimizes the total number of coins needed to obtain amount ss.

      ds=mini[[1,k]]dsci>0{dsci+1}\boxed{d_s=\underset{\substack{\\i\in[\![1, k]\!]\\d_{s-c_i}>0}}{\textrm{min}}\Big\{d_{s-c_i}+1\Big\}}

    • Case i,dsci=0\forall i, d_{s-c_i} = 0: We cannot obtain amount ss using coins cic_i.

      At the end of this step, amounts s{1,..,S}s\in\{1, .., S\} with ds=0d_s=0 cannot be obtained with the given coins.

The answer to this problem is given by dSd_S.

Want more content like this?

Subscribe here to be notified of new Super Study Guide releases!