Compsci 102: Knapsack problem Dynamic solution: How does it work?

I’m trying to get through the article on dynamic programming and the knapsack problem, and I have no idea what the dynamic program is doing or how it works. I even walked through and calculated all the values by hand and I still don’t understand what’s going on. Can someone please convince me that this is not black magic?

Here is the article:
https://www.codecademy.com/paths/computer-science/tracks/cspath-cs-102/modules/dynamic-programming/articles/the-knapsack-problem-python

Here is the Solution Code:

def dynamic_knapsack(weight_cap, weights, values):
  rows = len(weights) + 1
  cols = weight_cap + 1
  # Set up 2D array
  matrix = [ [] for x in range(rows) ]

  # Iterate through every row
  for index in range(rows):
    # Initialize columns for this row
    matrix[index] = [ -1 for y in range(cols) ]

    # Iterate through every column
    for weight in range(cols):
      # Write your code here
      if index == 0 or weight == 0:
        matrix[index][weight] = 0
      # If weight at previous row is less than or equal to current weight
      elif weights[index - 1] <= weight:
        # Calculate item to include
        include_item = values[index - 1] + matrix[index - 1][weight - weights[index - 1]]

        # Calculate item to exclude
        exclude_item = matrix[index - 1][weight]

        # Calculate the value of current cell
        matrix[index][weight] = max(include_item, exclude_item)
      else:
        # Calculate the value of current cell
        matrix[index][weight] = matrix[index - 1][weight]
  # Return the value of the bottom right of matrix
  return matrix[rows-1][weight_cap]

# Use this to test your function:
weight_cap = 50
weights = [31, 10, 20, 19, 4, 3, 6]
values = [70, 20, 39, 37, 7, 5, 10]
print(dynamic_knapsack(weight_cap, weights, values))

Hi,

Dynamic programming really requires good grounding on a few ideas for it to feel manageable, and even then it can be hard (depending on the task at hand). There’s nothing fuzzy or black magic about it in the end. With deliberate practice you can conquer it.

Let’s start with a more focused idea: How comfortable are you with the tools that dynamic programming works with?

  • recursion
  • structure (as in mathematical structure of the problem)
  • invariants (conditions that maintain a truth value over a substructure)
  • time complexity

Have you done other simpler dynamic programming problems (classic examples are fibonacci, staircase, rod-cutting)?

Without knowing a little more detail it’s hard to focus the advice… so I’ll try my best to cover overall cases.

A few general tips:

  • look for leetcode easy problems on dynamic programming, there aren’t many so maybe even do all of them before this one (and to be fair they’re not that easy). Try doing them with recursive dp and bottom-up dp. Then at least you know it’s not dynamic programming, but this problem’s specific complexity that is challenging.
  • watch some lectures on dynamic programming (MIT ones are a good start). The more advanced you go into algorithms the more abstraction and perspective help. A solution to one problem rarely offers insight into the family of problems or use-cases, etc.
  • find a really solid book on this stuff. Books can be difficult to digest (particularly the more proof-heavy ones) but the effort goes a long way to building technique and intuition. Sedgewick and CLRS are classics, but there are many others I’m sure.
  • practice dynamic programming consistently every day, even if just a bit (10 minutes, 20 minutes). Von Neumann has a wonderful quote people here are probably tired of me sharing but I think it’s wonderful and doesn’t stop inspiring me, it’s roughly: “…in mathematics you don’t understand things. You just get used to them”.
  • pen and paper (or whiteboard) are your very powerful friends. If you can draw the problem and walk through it visually, then the code will flow much easier.
2 Likes

I’ll also add that familiarity with depth-first-search and basic graph theory is another fundamental thing that helps a lot with dp.