What information is this table holding?
I know the description says:
Essentially, we want to find the maximum profit for every sub-array and every possible capacity. This means that
dp[i][c]will represent the maximum knapsack profit for capacity ‘c’ calculated from the first ‘i’ items.
But can someone describe this another way? What sub-array is this referring to?
I also don’t understand this formula.
dp[i][c] = max (dp[i-1][c], profit[i] + dp[i-1][c-weight[i]])
Hope this helps 
A value placed at dp[i][c] is the maximum profit we can get given that we have items till index ‘i’ to fill the knapsack of capacity ‘c’.
{0} -> one Item placed at index 0, number of items=1
{0,1} -> Items till index 1, number of items=2
{0, 1, 2} -> Items till index 2, number of items=3
{0, 1, 2, 3}) -> Items till index 3, number of items=4
dp[0][0] -> Given that we have one item {0} (placed at index 0) and a knapsack with 0 capacity(no knapsack) -> the maximum profit will be 0 because we don’t have any capacity. I have one item to put in the knapsack but how can I put this item if I don’t have a knapsack. ZERO CAPACITY MEANS WE DON’T HAVE A KNAPSACK. Profit will be 0 when we have a knapsack with zero capacity, regardless of the number of items that we have.
dp[1][0] -> Given that we have two items {0,1} and a knapsack with 0 capacity -> the maximum profit is still 0 because we don’t have any capacity in the knapsack.
dp[2][0] -> Given that we have three items {0, 1, 2} and a knapsack with 0 capacity -> Now, we have three items but the maximum profit is still 0 because we don’t have any capacity in the knapsack and we can’t fill the items.
Similarly, dp[3][0] equals 0.
dp[0][1] -> Given that we have one item {0} with weight 1 and a knapsack with capacity 1 -> the item’s weight meets the capacity requirement that we have, so we will fill the knapsack with this item and we will get the profit equals 1 and this is the maximum profit that we can get with the given inputs.
dp[0][2] -> Given that we have one item {0} with weight 1 and a knapsack with capacity 2 -> The maximum profit that we can get is still 1 because we have only one item(with profit =1) to fill the knapsack. We can’t use the remaining capacity(in this case it is 1) until we don’t have enough items with enough weights to fill the knapsack in order to get the maximum profit.
Similarly,
dp[0][3]=1(unused capacity=2)
dp[0][4]=1(unused capacity=3)
dp[0][5]=1(unused capacity=4)
dp[0][6]=1(unused capacity=5)
dp[0][7]=1(unused capacity=6)
dp[1][1] -> Given that we have two items {0, 1} with weights {1, 2}, and a knapsack with capacity 1 -> Now, we have more items with increased weight(1+2=3) to fill the knapsack but we don’t have enough capacity in the knapsack. i) We can’t fill the knapsack with item at index 1 because it’s weight is more than the knapsack’s capacity. So, we will exclude this item, and the maximum profit that we can get from the rest of the items (which in this case is items till index 0) with the given capacity is dp[0][1] . Remember we already calculated this value and that value is 1. Here we are going with dp[i-1][c] from the equation. profit[i] + dp[i-1][c-weight[i]] will be excluded because of [c-weight[i]] as it would be a negative value [1-2]=-1 which is an invalid index.
dp[1][2] -> Given that we have two items {0, 1} with weights {1, 2}, and a knapsack with capacity 2 -> Here [c-weight[i]] will give a positive value which indicates that we have enough capacity in the knapsack that we can put the item at index 1 in the knapsack. So, we will now add profit[i] which is 6, the capacity has been completely used(c=2 and weight[1]=2) so [c-weight[i]] will evaluate to 0 and dp[i-1][c-weight[i]] (dp[0][0]) is equal to 0. Remember we already computed this value. max(1, 6+0)=6, so the maximum profit is 6.
Similarly, we can fill the values in the rest of the table.