Raiders of the Lost Salary Cap

Indiana Jones has broken into an ancient temple and wants to bring back as much highly valued treasure to the university museum. There is a vast variety of items to choose from, each with a particular value. But his treasure sack can hold only 20 pounds of loot, so he needs to choose wisely. Should he take just a couple heavy but highly valuable items, or should he take several lighter but less valuable items?

It all depends on the particular values and weights of the items, but even if we knew those details with precision the problem becomes very complicated beyond a handful of potential items. Even with only 12 items to choose from, there are 2^12 = 4096 possible combinations of booty.

This happens to be a classic optimization problem, known unsurprisingly as the knapsack problem. Solving the knapsack problem tells you exactly which items Indiana should grab to bring back the most valuable collection of items possible. As you may imagine, this problem has many real-world applications, one of which will become fairly obvious in a moment.

Imagine that instead of Indiana Jones we’re talking about a GM. And instead of items of treasure we’re talking about players. Instead of weight we’re talking about salaries. And instead of the treasure sack and its weight limit, we’re talking about a salary cap.

Read more: Raiders of the Lost Salary Cap