# DP - 01 Knapsack problem

Given an array of weight `[w0, w1, w2...]`

and an array of value `[v0, v1, v2...]`

for some items. Pick some items to fill up a backpack whose maximum capacity is `N`

, with the biggest sum of values.

**Note:**

- DP formula is
`DP[i][j] = max(DP[i-1][j], DP[i-1][j-weight[i] + value[i])`

.- Explanation: Use a 2D array to represent items and weights.
`DP[i][j]`

means the max value of selecting items from`0 - i`

and adding them to a bag whose max capacity is`j`

. - There are two situations for item
`i`

- pick it or not.- Not select
`i`

, then the sum of value is the same of selecting from`0`

to`i-1`

. - Select
`i`

, then the sum of value is equal to selecing from`0`

to`i-1`

but substracting the weight of`i`

from the bag.

- Not select

- Explanation: Use a 2D array to represent items and weights.

**How to initialize DP:**

1 | /** |