Problem Description:
Given a set of 'n' items where each item 'i' has a weight and a value (wi, vi) and a knapsack with a maximum capacity 'W', what subset of items maximises the total value of the knapsack without exceeding it's weight limit.
\[
\begin{aligned}
&\text{Maximize} && \sum_{i=1}^n v_i x_i \\
&\text{subject to} && \sum_{i=1}^n w_i x_i \leq W, \\
& && x_i \in \{0,1\}, \quad i = 1, \dots, n
\end{aligned}
\]
Uniformally generates random solutions over a given time period, and stores the best valid solution.
Loops in binary from 0 to 2n-1 (over all possible individual subsets) and stores the best valid solution.
Time Complexity: \( \mathcal{O}(2^n) \)
Recursively solves the problem, by splitting it into smaller sub-problems, using the recursive idea below:
$$
k(W, n) =
\begin{cases}
0, & \text{if } W \le 0 \ \text{or} \ n \ge N, \\[6pt]
k(W,\, n+1), & \text{if } w_n > W, \\[6pt]
\max\left(
\underbrace{v_n + k(W - w_n,\, n+1)}_{\text{Include item}},\;
\underbrace{k(W,\, n+1)}_{\text{Exclude item}}
\right), & \text{otherwise}.
\end{cases}
$$
Time Complexity: \( \mathcal{O}(2^n) \)
Sorts the items in descending order based upon their value/weight ratio. The algorithm then loops through the list until no more items can be packed.
Time Complexity: \( \mathcal{O}(nlogn) \)
Due to the problem having an overlapping sub-problem structure, the memoization technique stems from the recursive approach but caches the results of previous sub-problems, and looks them up before recomputing therefore avoiding redundant calculations.
Time Complexity: \( \mathcal{O}(nW) \)
Tabulation creates a table and builds it up starting with resolving the smallest sub-problems until the main problem is solved.
Time Complexity: \( \mathcal{O}(nW) \)
We use the greedy approach to generate upper and lower bounds for the knapsack problem, and then prune branches to reduce the search space. We always explore the most promising sub-problems first.
Inspired by natural life processes such as the social behaviour of birds flocking or fish schooling, a population (swarm) of candidate solutions is called particles, where each particle has a position and velocity value over the search space. Each particle is influenced by its own best and the global best known solution in order to explore the search space.
Simulates natural selection across multiple candidate solutions. Each generation, crossover between solutions and mutation occurs. Selection techniques combined with elitism are used to pick the best solutions for the next generation. This process repeats over a large number of generations, keeping track of the best valid solution.
ACO is inspired by the behaviour of ants when searching for food. Each ant lays down a pheremone trail (a type of hormone) when exploring a particular path. Over time, good/frequently chosen paths will accumulate pheromone, attracting more ants. Additionally, the choices a 'path' takes is influenced by other heuristic information (attractiveness). Evapouration of pheromone occurs, so that older suboptimal paths lose influence over time.
