Lesson 1

The knapsack problem is a classic combinatorial optimization problem. It has a vast number of practical applications and, therefore, has been extensively studied. To demonstrate the main ideas of accelerating enumeration, we will consider the simplest version of the knapsack problem here: from a given set of numbers, we need to choose a subset such that its sum is, on the one hand, as large as possible and, on the other hand, does not exceed a given bound. The name of the problem comes from this real-life interpretation: there is a set of gold bars of different weights and a backpack that can hold a certain weight; the goal is to pack as much gold as possible into the backpack without exceeding the weight limit.

In a more general formulation of the knapsack problem, each item has not only a weight but also a value, and we want to maximize the total value under a weight constraint. In other words, we are dealing not with gold bars, but with arbitrary goods that differ in both weights and values. Many real-life problems reduce to this formulation. Here are a couple of examples:

• We want to fill a two-minute prime-time television slot with commercials. We have many offers from advertisers: each commercial has a duration and a price that will be paid for airing it.


• We have a limited budget that we want to spend to buy as much computing power as possible. We choose from a set of computers, each with its own performance and price.