Introduction to the knapsack problem

The knapsack problem is a good place to start when learning how to solve real-world combinatorial optimization problems that have constraints.

There are many types of knapsack problems, but we will only focus on the 0/1 knapsack problem with integer weights. In this case, we have a certain number of items with given weights and values, and our objective is to fit as many items in the knapsack as possible to maximize the value. The items that are not added to the knapsack have a value of 0, while those that fit in the knapsack have a value of 1. Of course, this means we would want to add all the items; however, we have a constraint on the total weight that we can place in the knapsack. This makes the problem considerably harder to solve, even though many solvers can solve this efficiently.

Each item in the knapsack is represented by xi, and each has a value, vi. The objective is to maximize the total value, V, of items, xi, placed inside the...