Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: The Knapsack Problem

Explore how to solve the knapsack problem by applying top-down dynamic programming with memoization. Understand the recursive approach, recognize optimal substructure and overlapping subproblems, and learn to optimize time complexity by storing intermediate results.

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 ...