# 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.

How to initialize DP: