0-1 Knapsack Problem

The 0-1 Knapsack Problem is a 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. The 0-1 comes from the restriction that only one copy of each valuable item can be added, i.e. an item is either inside the backpack (1) or not (0).

Problem Description(s) §

Decision Version §

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

Is NP-Complete

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

Solutions §

Brute-force approach §

A brute-force approach is:

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

This is equivalent to testing the Power Set of the items in the knapsack.

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

Dynamic Programming approach §

#todo

Analysis §

Time Complexity §

Approach	Time Complexity
Brute-force	$O(2^n)$