harishv7
1/9/2018 - 3:51 PM

0-1 Knapsack - Bottom Up

0-1 Knapsack - Bottom Up

```python
def knap_sack_bottom_up(w, weights, values, n):
    # the rows represent the nth item, the columns represent the wth weight
    arr = [[0 for x in range(w + 1)] for x in range(n+1)]
    # build up the table with bottom-up approach
    for i in range(n+1):
        for j in range(w+1):
            # When number of items to consider is 0 (i = 0)
            # and when weight is 0, we cannot put anything into the knapsack
            if(i == 0 or j == 0):
                arr[i][j] = 0
            elif(weights[i-1] <= j):
                # if the current item (ith item's) weight is within the current capacity we are considering (j), we check the max
                # j-weights[i-1] means we take the current capacity and minus of the ith items weight. Let's call this w2. Now we check w2 col for i-1 items.
                arr[i][j] = max(values[i-1] + arr[i-1][j-weights[i-1]], arr[i-1][j])
            else:
                arr[i][j] = arr[i-1][j]
    return arr[n][w]
```