Algorithms for Coding Interviews in Python/

...

/

Solution: The 0/1 Knapsack Problem

Solution: The 0/1 Knapsack Problem

This review provides a detailed analysis of the different ways to solve the knapsack problem.

We'll cover the following...

Solution 1: brute force

def knap_sack_recursive(profits, profits_length, weights, capacity, current_index):
    """
    Finds the maximum value that can be put in a knapsack
    :param profits: The profit that can be gained by each item
    :param profits_length: The number of pieces of jewelry
    :param weights: The weight of each piece of jewelry
    :param capacity: The maximum weight that the knapsack can hold
    :param current_index: Current index of the weights
    :return: Maximum value that can be put in a knapsack
    """
    # Base Case
    if capacity <= 0 or current_index >= profits_length or current_index < 0:
        return 0
    # If weight of the nth item is more than Knapsack, then
    # this item cannot be included in the optimal solution
    profit1 = 0
    if weights[current_index] <= capacity:
        profit1 = profits[current_index] + knap_sack_recursive(profits, profits_length, weights,
                                                     capacity - weights[current_index], current_index + 1)
    profit2 = knap_sack_recursive(profits, profits_length, weights, capacity, current_index + 1)
    # Return the maximum of two cases:
    # (1) nth item included
    # (2) not included
    return max(profit1, profit2)
def knap_sack(profits, profits_length, weights, capacity):
    """
    Finds the maximum value that can be put in a knapsack
    :param profits: The profit that can be gained by each
    :param profits_length: The number of pieces of jewelry
    :param weights: The weight of each piece of jewelry
    :param capacity: The maximum weight that the knapsack can hold
    :return: Maximum value that can be put in a knapsack
    """
    return knap_sack_recursive(profits, profits_length, weights, capacity, 0)
# Driver code to test the above function
if __name__ == '__main__':
    profits = [1, 6, 10, 16]  # The values of the jewelry
    weights = [1, 2, 3, 5]  # The weight of each
    print("Total knapsack profit = ", knap_sack(profits, 4, weights, 7))
    print("Total knapsack profit = ", knap_sack(profits, 4, weights, 6))

Explanation

We start from the beginning of the weight list and check if the item is within the maximum capacity on line 20.

For each item ii starting from the end:

  • create a new set which INCLUDES item ‘i’ if the total weight does not exceed the capacity and recursively process the remaining capacity and items. Save the result in profit1(line 20).
  • create a new set WITHOUT item ‘i’, recursively process the remaining items, and save the result in the variable, profit2(line 23).

Return the set from the above two sets with higher profit (line 28).

Let’s draw the recursive calls to see if there are any overlapping subproblems. As we can see, in each recursive call, the profits and weights lists remain constant and only the capacity and the current index change. For simplicity, let’s denote capacity with j and current index with n:

%0 node_1 n:3, C:2 node_1564986109026 n:2, C:2 node_1->node_1564986109026 node_1564986096422 n:2, C:1 node_1->node_1564986096422 node_1564986088297 n:1, C:2 node_1564986109026->node_1564986088297 node_1564986126161 n:1, C:1 node_1564986109026->node_1564986126161 node_1564986143001 n:0, C:2 node_1564986088297->node_1564986143001 node_1564986178691 n:0, C:1 node_1564986088297->node_1564986178691 node_1564986281341 n:0, C:1 node_1564986126161->node_1564986281341 node_1564986337916 n:0, C:0 node_1564986126161->node_1564986337916 node_1564986169528 n:1, C:1 node_1564986096422->node_1564986169528 node_1564986116942 n:1, C:0 node_1564986096422->node_1564986116942 node_1564986689501 n:0, C:1 node_1564986169528->node_1564986689501 node_1564986382417 n:0, C:0 node_1564986169528->node_1564986382417

Time complexity

The time complexity of the algorithm above is O(2n)O(2^n)—i.e., exponential—where nn is the total number of items. This is because we will have that many calls. This is owing to the overlapping subproblems. Let’s see how we can reduce it with a dynamic programming approach.

Solution 2: top-down dynamic programming approach with memoization

def knap_sack_recursive(lookup_table, profits, profits_length, weights, capacity, current_index):
    """
    Finds the maximum value that can be put in a knapsack
    :param profits: The profit that can be gained by each
    :param profits_length: The number of pieces of jewelry
    :param weights: The weight of each piece of jewelry
    :param capacity: The maximum weight that the knapsack can hold
    :param current_index: Current index of the weights
    :return: Maximum value that can be put in a knapsack
    """
    # base checks
    if capacity <= 0 or current_index >= profits_length or current_index < 0:
        return 0
    # if we have already solved the problem, return the result from the table
    if lookup_table[current_index][capacity] != 0:
        return lookup_table[current_index][capacity]
    # recursive call after choosing the element at the current_index
    # if the weight of the element at current_index exceeds the capacity, we shouldn't process this
    profit1 = 0
    if weights[current_index] <= capacity:
        profit1 = profits[current_index] + knap_sack_recursive(lookup_table, profits,
                                                               profits_length, weights,
                                                               capacity - weights[current_index],
                                                               current_index + 1)
    # recursive call after excluding the element at the current_index
    profit2 = knap_sack_recursive(lookup_table, profits, profits_length,
                                  weights, capacity, current_index + 1)
    lookup_table[current_index][capacity] = max(profit1, profit2)
    return lookup_table[current_index][capacity]
def knap_sack(profits, profits_length, weights, capacity):
    """
    Finds the maximum value that can be put in a knapsack
    :param profits: The profit that can be gained by each
    :param profits_length: The number of pieces of jewelry
    :param weights: The weight of each piece of jewelry
    :param capacity: The maximum weight that the knapsack can hold
    :return: Maximum value that can be put in a knapsack
    """
    lookup_table = [[0 for x in range(capacity + 1)] for x in range(profits_length + 1)]
    return knap_sack_recursive(lookup_table, profits, profits_length, weights, capacity, 0)
# Driver code to test the above function
if __name__ == '__main__':
    profits = [1, 6, 10, 16]  # The values of the jewelry
    weights = [1, 2, 3, 5]  # The weight of each
    print("Total knapsack profit = ", knap_sack(profits, len(profits), weights, 7))
    print("Total knapsack profit = ", knap_sack(profits, len(profits), weights, 6))

Explanation

The function knap_sack ...