Knapsack Problem

algorithms

Definition

Knapsack Problem

The knapsack problem asks for filling a fixed-size knapsack with elements that have a size and a value such that the value of the knapsack is maximised. Greedy algorithms on the value of the elements won’t work here.

Approaches

Dynamic Programming

The knapsack problem is a classic example for using dynamic programming for a problem. Given $n$ items, where each item has a size and a value, you try to solve all sub-problems for $i=n-1,n-2,\dots$. During solving this problem, a table is built:

$i/w$	0	1	2	…	$w$
0	0	0	0	…	0
1				…
2				…
…	…	…	…	…	…
$n$				…

After the DP table is built, the algorithm just chooses based on the table dp[n][max_size].

TL;DR: Dynamic Programming Approach

The dynamic programming approach solves the problem for all $0\le i\le n$ and $0\le w\le \text{max\_size}$, builds up a table and picks the solution for the desired problem.

Solutions of smaller problems can be used for the next bigger problem, until the desired problem is picked.

---

Python

def knapsack(
			 max_size: int,
			 items: list[tuple[int, int]],
 ) -> int:
	n: int = len(items)
	dp: list[list[int]] = [
		[0] * (max_size + 1)
		for _ in range(n + 1)
	]
	for i in range(1, n + 1):
		item_size, item_value = items[i - 1]
			for w in range(max_size + 1):
				if item_size <= w:
					dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - item_size] + item_value)
				else: dp[i][w] = dp[i - 1][w]
	return dp[n][max_size]