# The knapsack 0-1 problem

1. State
$dp_{i,w}=$ $true$ or $false$
Can we take some of the first $i$ bars in such a way that its total weight would be exactly $w$?
2. Base
$dp_{0,0} = true$
$dp_{0,i} = false$
4. Transition formula
$dp_{i,w} = dp_{i-1, w}$ or $dp_{i-1, w-w_i}$ if $w_i \le w$
5. Order of iterating
By increasing of $i$, then by increasing of $w$.
7. Answer
Maximal such a weight $w$ that $dp_{n, w}$ is $true$.