Frame by Frame: In the Jaws of the Knapsack Algorithm

About 2 hours 4 mins. That’s it. That’s the time it took an entire country to be forever terrified of sharks. The director, Steven Spielberg had only about 2 hours to create a blockbuster that would go down in the history of cinema as “one of the scariest movies of all time”. Which scenes would he chose to fit in? Which scenes would he include to create the maximum impact on the audience? Every scene has a cost - screen time.

This is exactly where Knapsack algorithm comes into play.

The Knapsack algorithm is something that, although sounds daunting, but is quite the easiest algorithm in the book of algorithms; i.e. once you get to know its secret.

I shall be explaining and breaking down the logic of this algorithm step by step, or rather frame by frame.

Before that, a little background story.

The term “Knapsack” comes from the German word, “knappen” which literally means “to bite”. Experts believe it was used by the soldiers to carry food in their knapsack. Knapsack typically refers to a bag that is used to carry stuff.

Now, the rules for this algorithm are simple. If you’re given a set of items, each with a value and weight, one has to determine which items to include in a collection so as to satisfy two conditions:

1. the total weight ≤ Given limit
2. total value must be as large as possible.

The aim here is to identify which items to keep in a knapsack so as to gain maximum profit, much like a director decides which scenes must go in a movie to make it a much valuable blockbuster hit.

So let’s go back to Spielberg. His knapsack? The film itself. His weight limit? The duration of the movie. His items? All the scenes he shot, each with a screen time and audience impact. His aim? Maximum Blockbuster.

So, say, there are three scenes shot at different time duration for one scary bit. The maximum screen time for one scary scene in that movie is 10 minutes. Which one of the three makes the final cut?

Table 1.1: A specimen table that helps to understand the logic of Knapsack Algorithm

A formula may ease things up a bit:

Fig 1. 1: The Knapsack Algorithm Formula

Now don’t you start fretting on how this looks like Elvish. I assure you it’s not. Here,

1. “m” stands for maximum weight given (in this case, the maximum screen time for one scene) .
2. “n” is the no of items (in this case, the number of scenes).
3. “wₙ” is the weight given (in this scenario, the time duration of each scene).
4. “Pₙ” is the profit given for that particular item. (in this case, the impact).

With these two properties:

So, here’s how to decide which scene makes the cut?

Step 1: Start with maximum value. Here, n=3 and m=6.

Step 2: Put the values to construct a formula. Like this:

Fig 1.2: The formulaic manner to solve the problem

Here, this is how it works behind the scenes:

Fig 1.3: The colors are used to represent which one to use

Step 3: The brown coloured value “f₀(-1)” is equal to -∞ as per property.

Step 4: Substitute the values and just start solving from backwards like this:

Fig 1.4: Solve the formulas by substituting values from Fig 1.2

The highlighted “10” shows that they are the maximum profit we can gain out of the entire calculated algorithm.

So, either shot 2 with 5 minutes or shot 3 with 2 minutes will be perfect in a maximum 6 minute scary sequence (which i know is a lot, but for the sake of explanation).

And just like that… Spielberg solved his dilemma. The Knapsack Algorithm chose either of the shot 2 or 3 to give out the maximum scare to the audience.

The Beach scene? Cut. Not because its bad- but because the algorithm knows better. Maximum profit yet minimum waste. Just like every blockbuster movie.

That’s the beauty of the Knapsack Algorithm. It manages to give answers for dilemmas like these and maybe that’s why Jaws managed to scare an entire generation of people in exactly 2 hours and 4 minutes. Every scene that made it through- earned its place, frame by frame.

P.S: I’m still learning and so is this blog. 😄If you spot any errors or have a better way to explain this, please drop a comment! Afterall, “To err is human; to forgive, divine — Alexander Pope”