DSA The 0/1 Knapsack Problem

The 0/1 Knapsack Problem

The 0/1 Knapsack Problem states that you have a backpack with a weight limit, and you are in a room full of treasures, each treasure with a value and a weight.

To solve the 0/1 Knapsack Problem you must figure out which treasures to pack to maximize the total value, and at the same time keeping below the backpack's weight limit.

Bravo! You found the items that gives the maximum value😀

1

2

3

Knapsack

$ {{ totalValue }}

{{ totalWeight }}/{{limit}} kg

{{ item.name }}

$ {{ item.value }}

{{ item.weight }} kg

Are you able to solve the 0/1 Knapsack Problem above manually? Continue reading to see different implementations that solves the 0/1 Knapsack Problem.

Solving the 0/1 Knapsack Problem helps businesses decide which projects to fund within a budget, maximizing profit without overspending. It is also used in logistics to optimize the loading of goods into trucks and planes, ensuring the most valuable, or highest prioritized, items are included without exceeding weight limits.

The Brute Force Approach

Using brute force means to just check all possibilities, looking for the best result. This is usually the most straight forward way of solving a problem, but it also requires the most calculations.

To solve the 0/1 Knapsack Problem using brute force means to:

1. Calculate the value of every possible combination of items in the knapsack.
2. Discard the combinations that are heavier than the knapsack weight limit.
3. Choose the combination of items with the highest total value.

This brute force approach to the 0/1 Knapsack problem can be implemented like this:

def knapsack_brute_force(capacity, n):
    print(f"knapsack_brute_force({capacity},{n})")
    if n == 0 or capacity == 0:
        return 0

    elif weights[n-1] > capacity:
        return knapsack_brute_force(capacity, n-1)

    else:
        include_item = values[n-1] + knapsack_brute_force(capacity-weights[n-1], n-1)
        exclude_item = knapsack_brute_force(capacity, n-1)
        return max(include_item, exclude_item)

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

print("\nMaximum value in Knapsack =", knapsack_brute_force(capacity, n))

Running the code above means that the knapsack_brute_force function is called many times recursively. You can see that from all the printouts.

Every time the function is called, it will either include the current item n-1 or not.

Line 2: This print statement shows us each time the function is called.

Line 3-4: If we run out of items to check (n==0), or we run out of capacity (capacity==0), we do not do any more recursive calls because no more items can be added to the knapsack at this point.

Line 6-7: If the current item is heavier than the capacity (weights[n-1] > capacity), forget the current item and go to the next item.

Line 10-12: If the current item can be added to the knapsack, see what gives you the highest value: adding the current item, or not adding the current item.

Running the code example creates a recursion tree that looks like this, each gray box represents a function call:

From the recursion tree above, it is possible to see that for example taking the crown, the cup, and the globe, means that there is no space left for the microscope (2 kg), and that gives us a total value of 200+400+500=1100.

We can also see that only taking the microscope gives us a total value of 300 (right bottom gray box).

As you can see in the recursion tree above, and by running the example code, the function is sometimes called with the same arguments, like knapsack_brute_force(2,0) is for example called two times. We avoid this by using memoization.

The Memoization Approach (top-down)

The memoization technique stores the previous function call results in an array, so that previous results can be fetched from that array and does not have to be calculated again.

Read more about memoization here.

Memoization is a 'top-down' approach because it starts solving the problem by working its way down to smaller and smaller subproblems.

In the brute force example above, the same function calls happen only a few times, so the effect of using memoization is not so big. But in other examples with far more items to choose from, the memoization technique would be more helpful.

After improving the brute force implementation with the use of memoization, the code now looks like this:

def knapsack_memoization(capacity, n):
    print(f"knapsack_memoization({n}, {capacity})")
    if memo[n][capacity] is not None:
        print(f"Using memo for ({n}, {capacity})")
        return memo[n][capacity]
    
    if n == 0 or capacity == 0:
        result = 0
    elif weights[n-1] > capacity:
        result = knapsack_memoization(capacity, n-1)
    else:
        include_item = values[n-1] + knapsack_memoization(capacity-weights[n-1], n-1)
        exclude_item = knapsack_memoization(capacity, n-1)
        result = max(include_item, exclude_item)

    memo[n][capacity] = result
    return result

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
n = len(values)

memo = [[None]*(capacity + 1) for _ in range(n + 1)]

print("\nMaximum value in Knapsack =", knapsack_memoization(capacity, n))

The highlighted lines in the code above show the memoization technique used to improve the previous brute force implementation.

Line 24: Create an array memo where previous results are stored.

Line 3-5: At the start of the function, before doing any calculations or recursive calls, check if the result has already been found and stored in the memo array.

Line 16: Store the result for later.

The Tabulation Approach (bottom-up)

Another technique to solve the 0/1 Knapsack problem is to use something called tabulation. This approach is also called the iterative approach, and is a technique used in Dynamic Programming.

Tabulation solves the problem in a bottom-up manner by filling up a table with the results from the most basic subproblems first. The next table values are filled in using the previous results.

Use the animation below to see how the table is filled cell by cell using previously calculated values until arriving at the final result.

The tabulation approach works by considering one item at a time, for increasing knapsack capacities. In this way the solution is built up by solving the most basic subproblems first.

On each row an item is considered to be added to knapsack, for increasing capacities.

def knapsack_tabulation():
    n = len(values)
    tab = [[0]*(capacity + 1) for y in range(n + 1)]

    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w-weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]
    
    for row in tab:
    	  print(row)
    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

Line 7-10: If the item weight is lower than the capacity it means it can be added. Check if adding it gives a higher total value than the result calculated in the previous row, which represents not adding the item. Use the highest (max) of these two values. In other words: Choose to take, or not to take, the current item.

Line 8: This line might be the hardest to understand. To find the value that corresponds to adding the current item, we must use the current item's value from the values array. But in addition, we must reduce the capacity with the current item's weight, to see if the remaining capacity can give us any additional value. This is similar to check if other items can be added in addition to the current item, and adding the value of those items.

Line 12: In case the current item is heavier than the capacity (too heavy), just fill in the value from the previous line, which represents not adding the current item.

Manual Run Through

Here is a list of explanations to how a few of the table values are calculated. You can click the corresponding table cell in the animation above to get a better understanding as you read.

Microscope, capacity 1 kg: For the first value calculated, it is checked whether the microscope can be put in the bag if the weight limit is 1 kg. The microscope weighs 2 kg, it is too heavy, and so the value 0 is just copied from the cell above which corresponds to having no items in the knapsack. Only considering the microscope for a bag with weight limit 1 kg, means we cannot bring any items and we must leave empty handed with a total value of $ 0.

Microscope, capacity 2 kg: For the second value calculated, we are able to fit the microscope in the bag for a weight limit of 2 kg, so we can bring it, and the total value in the bag is $ 300 (the value of the microscope). And for higher knapsack capacities, only considering the microscope, means we can bring it, and so all other values in that row is $ 300.

Globe, capacity 1 kg: Considering the globe at 1 kg and a knapsack capacity at 1 kg means that we can bring the globe, so the value is $ 200. The code finds the maximum between bringing the globe which gives us $ 200, and the previously calculated value at 1 kg capacity, which is $ 0, from the cell above. In this case it is obvious that we should bring the globe because that is the only item with such a low weight, but in other cases the previously calculated value at the same capacity might be higher.

Globe, capacity 2 kg: At capacity 2 kg, the code sees that the globe can fit, which gives us a value of $ 200, but then the microscope cannot fit. And adding the microscope for a capacity of 2 kg gives us a value of $ 300, which is higher, so taking the microscope (value from the cell above) is the choice to maximize knapsack value for this table cell.

Globe, capacity 3 kg: Considering the globe with a capacity of 3 kg, means that we can take the globe, but with the remaining capacity of 2 kg we can also take the microscope. In this cell, taking both the globe and the microscope gives us a higher value 200+300=500 than taking just the microscope (as calculated on the previous line), so both items are taken and the cell value is 500.

Which Items Gives Us The Highest Value?

After filling out the table and finding the maximum value the knapsack can have, it is not obvious which items we need to pack with us to get that value.

To find the included items, we use the table we have created, and we start with the bottom right cell with the highest value, in our case the cell with value 1200 in it.

Here is a drawing of how the included items are found, using the step-by-step method:

This is how the included items are found:

1. The bottom right value is 1200, and the cell above is 900. The values are different, which means the crown is included.
2. The next cell we go to is on the row above, and we move left as many times as the crown is heavy, so 3 places left to the cell with value 700.
3. The cell we are in now has value 700, and the cell above has value 500. The values are different, which means the item on the current row is included: the cup.
4. The cup weighs 5 kg, so the next cell we go to is on the row above, and 5 places to the left, to the cell with value 300, on the row were the globe is considered.
5. The cell above has the same value 300, which means the globe is not included, and the next cell we go to is the cell right above with value 300 where the microscope is considered.
6. Since the cell above is different than the current cell with value 300, it means the microscope is included.
7. The next cell we go to is on the line above, and two places to the left because the microscope is 2 kg.
8. We arrive at the upper leftmost cell. Since the value is 0, it means we are finished.

Our 0/1 Knapsack problem has maximum value when these items are included: the crown, the cup, and the microscope.

The same steps are added to the code below, to find the items that make up the solution to the 0/1 Knapsack problem.

def knapsack_tabulation():
    n = len(values)
    tab = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                include_item = values[i-1] + tab[i-1][w - weights[i-1]]
                exclude_item = tab[i-1][w]
                tab[i][w] = max(include_item, exclude_item)
            else:
                tab[i][w] = tab[i-1][w]

    for row in tab:
        print(row)

    items_included = []
    w = capacity
    for i in range(n, 0, -1):
        if tab[i][w] != tab[i-1][w]:
            items_included.append(i-1)
            w -= weights[i-1]

    print("\nItems included:", items_included)

    return tab[n][capacity]

values = [300, 200, 400, 500]
weights = [2, 1, 5, 3]
capacity = 10
print("\nMaximum value in Knapsack =", knapsack_tabulation())

Time Complexity

The three approaches to solving the 0/1 Knapsack Problem run differently, and with different time complexities.

Brute Force Approach: This is the slowest of the three approaches. The possibilities are checked recursively, with the time complexity \(O(2^n)\), where \(n\) is the number of potential items we can pack. This means the number of computations double for each extra item that needs to be considered.

Memoization Approach: Saves computations by remembering previous results, which results in a better time complexity \(O(n \cdot C)\), where \(n\) is the number of items, and \(C\) is the knapsack capacity. This approach runs otherwise in the same recursive way as the brute force approach.

Tabulation Approach: Has the same time complexity as the memoization approach \(O(n \cdot C)\), where \(n\) is the number of items, and \(C\) is the knapsack capacity, but memory usage and the way it runs is more predictable, which normally makes the tabulation approach the most favorable.