The Knapsack problem is a combinatorial optimization problem that comes from a real-life situation in computer science.
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
The problem is defined formally as follows:
- Inputs:
- n items are given, each with a weight w[i] and a value v[i]
- Maximum weight W
The task is to determine the maximum value that can be carried in the knapsack without exceeding weight W.
Here’s a mathematical formulation of the problem:
$$\begin{aligned}
\text{maximize:} & \sum\_{i=1}^{n} x\_i \cdot v\_i \\
\text{subject to:} & \sum\_{i=1}^{n} x\_i \cdot w\_i \leq W \\
\text{and:} & x\_i \in \{0,1\} \quad\text{for all } i\end{aligned}$$
The decision variable x_i is binary, indicating whether or not item i is included in the knapsack.
The problem can be solved by a dynamic programming algorithm:
1. Initialize a table K[][] of size n x W+1.
2. Build the table K[][] in bottom-up manner.
3. For each item i (from 1 to n):
- For each weight w (from 1 to W):
- If w[i] <= w, then compute max(v[i] + K[i-1][w-w[i]], K[i-1][w])
- Otherwise keep K[i-1][w]
The python code to solve the problem is as follows:
def knapSack(W, wt, val, n):
K = [[0 for w in range(W+1)]
for i in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1]
+ K[i-1][w-wt[i-1]],
K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]You call this function as knapSack(W, wt, val, n) where:
- val[] is the array of values,
- wt[] is the array of weights,
- W is the knapsack’s maximum weight,
- n is the number of items.
4. Return K[n][W] which contains the maximum value that can be carried in the knapsack.
This is a good solution but it is not efficient for large W (knapsack capacity). The time complexity of this algorithm is O(nW) where n is the number of items and W is the knapsack capacity. Both time and space complexity of the dynamic programming solution is O(nW). You should use this approach when the weight capacity is not too big.