Knapsack Problem

The Knapsack Problem is another famous optimisation problem studied in computer science. In this problem, the goal is to fit as many ‘valuable’ items in a limited-capacity knapsack (backpack) as it can hold. The goal is to maximise the total value of all the items in the knapsack, without exceeding it’s capacity.

Decision Version: NP-Complete §

Given a subset of items $S$ with values and weights, can a total value of $V$ be achieved, without exceeding weight $W$?

Optimisation Version: §

Given a subset of items $S$ with weights and values, what is the maximum value $V$ that can be obtained with the least weight $W$?

Exhaustive/Brute-force approach: $O(2^n)$ §

1. Every item can either be in the knapsack, or not in the knapsack.
2. Therefore we can say that each item has 2 states, and those are multiplied for a given combination

Therefore, we have a time complexity of $O(2^n)$, making this algorithm intractable.

Dynamic Programming §

#todo