Knapsack Problem

Last updated Nov 8, 2022 Edit Source

Given n items where the $i^{th}$ item has a weight $w_i$ and value $v_i$

Find the largest total value of items that fits in a knapsack of capacity $C$.

Let $P(C, j)$ be the max profit by selecting a subset of j objects with knapsack capacity C.

Base case: Capacity or number of items is 0 $$P(C,0)=P(0,j)=0 $$ Otherwise, the solution to a knapsack of capacity C can be found using the solutions to the subproblems of capacity $C-w_i$ for items $i=1 \to n$. For each item, we can choose either include or not include it in the knapsack: $$P(C,j)=max(P(C,j-i), P(C-w_j,j-1)+v_j) $$

Profit table:

Maximizing by the profit per weight: