Knapsack Problem

Inventory management, in other words

The Knapsack Problem is one of many types of combinatorial decision problems that are generally good to be aware of because it satisfies three conditions:

• Players understand it intuitively

• There aren’t easy/boring solutions to a lot of example problems

• It’s hard for most people to hack

This is my private definition of the “Tetris Effect”. It’s a problem that’s easy to understand, easy to play with, and very hard to solve optimally. Players can come up with solutions, often quite good ones, but they’ll generally know that they can do better if they engage with the problem for a bit longer.

So what is it?

The (basic) Knapsack Problem gives you a selection of items that have different values and weights. A gun is a valuable weapon, but it also weighs a lot. A paperclip isn’t as valuable, but it weighs a lot less. You have to decide which items to bring along with you on an adventure, but you can only carry so much weight.

You might need to check my post about summation notation to understand the formulation here (thanks Wikipedia!) but here it is:

Each item has an index i, a value to the player v, and a weight value w. The player also has a maximum weight carry of W and a switch value x which can either be 0 or 1. This x value decides whether or not the player is actually carrying each item or not.

The Knapsack problem is so ubiquitous in gaming that you’ll start seeing it everywhere once you know about it. The classic example is inventory management mechanics because you can literally visualise the Knapsack in question.

Resident Evil introduces a further wrinkle, instead of weight as the limiting factor, the total area is. Resi says to players, carry as much as you like, as long it fits. It’s a class of Knapsack Problem, but one with different constraints!

There are many other types of decision problems that are like this, and I’ll post more about those in the coming weeks! For now, enjoy noodling on this one!