# Solving 0-1 Knapsack Problems

## Introduction

The 0-1 knapsack problem is a classical computer science and optimization problem. The conventional optimal computer science strategy to solve it is dynamic programming. It can also be viewed as a simple linear programming problem and solved by specialized linear programming solver.

In this blog post, I reviewed the classical 0-1 knapsack problem, implemented three knapsack solvers, including a recursion solver, a dynamic programming solver, and a linear programming solver, and compared the performances ot the three knapsack solvers.

## 0-1 Knapsack Problem

The classical knapsack problem is defined as follows. Given a set of $n$ items numbered from $1$ up to $n$, each with a weight $w_i$ and a value $v_i$, along with a maximum weight capacity $W$, and a $0/1$ binary value $x_i$ indicating whether item $i$ is selected or not, the goal is to find out all the items subject to the maximum weight capacity that maximize the total value.

$$\DeclareMathOperator*{\argmin}{argmin} \DeclareMathOperator*{\argmax}{argmax} \argmax_{x_1, x_2, \cdots, x_n} \sum_{i=1}^{n} x_i v_i$$

subject to

$$\begin{gather} \sum_{i=1}^{n} x_i w_i \leq W \\ x_i \in \{0, 1\} \quad \forall i \in [1 \dotsc n] \\ \end{gather}$$

Notice that the optimization goal, the total value, is a linear function of $x_1, x_2, \cdots, x_n$. Because linear function is both convex and concave (please show a simple proof on your own), which implies that every local optimum is a global optimum. This means that the optimum solution from linear programming solver is global optimum.

## 0-1 Knapsack Solvers

Here I implemented three knapsack solvers using recursion, dynamic programming, and linear programming. The recursion solver is intractable and is therefore not quite useful when the number of items is large. The dynamic programming solver is a standard implementation for solving knapsack problems. However, it can only deal with 0-1 knapsack problems whose weights are integers. If the weights were not integers, they would have to be converted to integers before applying to the dynamic programming solver. The linear programming solver can be used for solving the knapsack problem because knapsack problem itself is a linear optimization problem. Some unit tests were also prepared for testing. For the convenience of testing all the solvers, the weights in the knapsack problems are all integers.

### Install Dependencies

We will install and use pulp and glpk linear programming solvers to solve knapsack problems.

### Knapsack Problem Solver Execution

Running the following program will print out the solution for the knapsack problem in the terminal.

We could see that when the number of items in the knapsack problems are large, the linear programming solver is about 100 times faster than the dynamic programming solver. Although such comparison is not fair since the linear programming solver utilizes C/C++ solver libraries behind the scene where the dynamic programming solver is implemented using pure Python, this at least unambiguously told us that writing a pure Python program to solve a knapsack problem is not a good strategy.

Lei Mao

02-13-2023

02-13-2023