0-1 Knapsack

Suppose you have \(n\) items, where the weight of the \(i\)th item is given by the integer weights[i] and the value of the \(i\)th item is given by the integer values[i]. You also have a knapsack that can hold any number of items as long as their total weight is less than or equal to weight \(W\). Write a function to return the maximum total value that can be attained for items placed in the knapsack.

Brute force

You can either include the last item in the knapsack if its weight is below the knapsack’s capacity or you can not include it. In the worst case, you have 2 choices for each item, so the time complexity is \(O(2^n)\). The space complexity is \(O(1)\).

def knapSack(W, wt, val, n):
    if n == 0 or W == 0:
        return 0
    
    value_if_last_item_not_included = self.knapSack(W, wt, val, n-1)
    
    if wt[n-1] > W:
        return value_if_last_item_not_included
    
    value_if_last_item_included = (
        val[n-1] + self.knapSack(W-wt[n-1], wt, val, n-1))

    return max(value_if_last_item_not_included, value_if_last_item_included)

Memoization

In the worst case, each item has weight 1 and the time complexity is \(O(nW)\). The space complexity is also \(O(nW)\).

def knapSack(W, wt, val, n, memo):
    if n == 0 or W == 0:
        return 0
    
    if (W, n-1) not in memo:
        memo[(W, n-1)] = knapSack(W, wt, val, n-1, memo)
    value_if_last_item_not_included = memo[(W, n-1)]
    
    if wt[n-1] > W:
        return value_if_last_item_not_included
    
    if (W-wt[n-1], n-1) not in memo:
        memo[(W-wt[n-1], n-1)] = knapSack(W-wt[n-1], wt, val, n-1, memo)
    value_if_last_item_included = val[n-1] + memo[(W-wt[n-1], n-1)]

    return max(value_if_last_item_not_included, value_if_last_item_included)

Tabulation

As with memoization, the time complexity is \(O(nW)\) and the space complexity is \(O(nW)\).

def knapSack(W, wt, val, n, memo):
    if n == 0 or W == 0:
        return 0

    tab = [[0 for _ in range(W+1)] for _ in range(n+1)]
    for m in range(1, n+1):    
        for w in range(1, W+1):
            if wt[m-1] > w:
                tab[m][w] = tab[m-1][w]
            else:
                tab[m][w] = max(tab[m-1][w], val[m-1] + tab[m-1][w-wt[m-1]])

    return tab[n][W]

You can get down to \(O(W)\) space complexity, because we only need to keep track of the result for some \(w\) for \(n-1\) and not all \(k < n\).

def knapSack(W, wt, val, n, memo):
    if n == 0 or W == 0:
        return 0

    tab = [0 for _ in range(W+1)]
    for m in range(1, n+1):    
        for w in range(W, -1, -1):
            if wt[m-1] <= w:
                tab[w] = max(tab[w], val[m-1] + tab[w-wt[m-1]])

    return tab[W]