# The Knapsack Problem

The knapsack problem is without a doubt a “must know” for any software professional. Wikipedia reports that “out of 75 algorithmic problems, the knapsack problem [is] the 19th most popular and the third most needed”1. Regardless of your particular domain, it’s highly probable that you will need to understand this algorithm’s particulars.

Suppose you have a number of items of varying size and value that you need to place inside a knapsack. Unfortunately, the knapsack isn’t large enough to hold all the items. You need a strategy for packing the knapsack with items that have the highest possible total value. Stated in computer science terms, you have $2n+1$ positive integers2. $n$ is the number of items. Each item has an associated value ($v_i$) and size ($s_i$). The final integer is the capacity ($C$) of the knapsack. This algorithm will select the subset of items with a total size lower than $C$ ($\sum_{i \in S} s_i \leq C$) that also has the maximum possible total value ($\max{\sum_{i \in S} v_i}$). This is best demonstrated with an example. Consider the image below. Consider the knapsack a convenient abstraction. This is a useful algorithm for any scenario where a scarce resource must be managed optimally.

## Applications

• Production scheduling
• Capital budgeting
• Portfolio management

## Asymptotic Complexity

$O(nC)$ where $n$ is the number of items and $C$ is the knapsack capacity.

## Pseudo Code

inputs:
S = array of sizes
V = array of values
C = capacity of knapsack
n = number of items

knapsack:
solutions[n + 1][C + 1]

for i = 0 to C:
solutions[i] = 0;

for i = 1 to n + 1:
for c = 0 to C + 1:
if S[i] < c:
solutions[i][c] = solutions[i - 1][c]
else if solutions[i - 1][c] > solutions[i - 1][S[i] + V[i]:
solutions[i][c] = solutions[i - 1][c]
else
solutions[i][c] = solutions[i - 1][S[i] + V[i]

return solustions[n][C];


Full Repo

Relevant Files: