Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: The Knapsack Problem

Solution Review: The Knapsack Problem

In this lesson, we will review the solution to the knapsack problem.

We'll cover the following...

Solution 1: Simple recursion

Python 3.5
def solveKnapsack(weights, prices, capacity, index):
  # base case of when we have run out of capacity or objects
  if capacity <= 0 or index >= len(weights): 
    return 0
  # if weight at index-th position is greater than capacity, skip this object
  if weights[index] > capacity: 
    return solveKnapsack(weights, prices, capacity, index + 1)
  # recursive call, either we can include the index-th object or we cannot, we check both possibilities and return the most optimal one using max
  return max(prices[index]+solveKnapsack(weights, prices, capacity - weights[index], index+1),
        solveKnapsack(weights, prices, capacity, index + 1))
def knapsack(weights, prices, capacity):
  return solveKnapsack(weights, prices, capacity, 0)
print(knapsack([2,1,1,3], [2,8,1,10], 4))

Explanation

Let’s go over the intuition of the problem before moving on to the explanation of the code. Remember your goal was to select a subset of objects which return the maximum total profit while obeying the constraint that their weight is less than or equal to the total capacity of the knapsack. Now any object, let’s say a book, either can or cannot be a part of the optimal subset. There cannot be any other possibility for this book, right? This is what we are doing in this solution. We make two recursive calls: one with an object included (line 9), and another without (line 10). Then we take the maximum of these two profit values. We continue doing this until we have either run out of capacity or objects (line 3). Along the way, if we reach a point where an object’s weight is greater than the capacity, we can skip over this object. Let’s see the following visualization for more clarification.

Time complexity

If we have n objects, we find every set where any object is either in the set or it is not. This means we are looking for all the possible subsets of a set of n objects. How many subsets exist for a set of ...