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.

sudo apt-get update
sudo apt-get install glpk-utils

pip install pulp==2.4

Python Implementation

knapsack.py

# 0-1 Knapsack Problem
import numpy as np
from timeit import default_timer as timer
from datetime import timedelta
from typing import List, Tuple, Union, Callable
from pulp import LpMaximize, LpProblem, LpStatus, lpSum, LpVariable, LpBinary, LpInteger
from pulp import GLPK


def knapsack_solver_recursion(
        values: List[Union[int, float]], weights: List[Union[int, float]],
        capacity: int) -> Tuple[Union[int, float], List[bool]]:

    # Time complexity: O(2^n)
    # Space complexity: O(1)
    # where n is the number of candidate items.
    # This is an intractable algorithm.
    # Easy to result in stack overflow.

    assert len(values) == len(weights)
    n = len(values)

    # There are two scenarios.
    # 1. The first item is in the optimal solution.
    # 2. The first item is not in the optimal solution.
    # If #1, then values[0] + knapsack_solver_recursion(values[1:], weights[1:], capacity-weights[0])[0] is the optimal total value.
    # If #2, then knapsack_solver_recursion(values[1:], weights[1:], capacity)[0] is the optimal total value.

    # Base cases
    # Only has 1 item.
    if n == 1:
        if weights[0] <= capacity:
            return values[0], [1]
        else:
            return 0, [0]

    # Recursive cases
    # Has more than 1 item.

    # If the first item is too big, so it must not in the optimal solution.
    if weights[0] > capacity:
        total_value, picks = knapsack_solver_recursion(values=values[1:],
                                                       weights=weights[1:],
                                                       capacity=capacity)
        picks = [0] + picks
        return total_value, picks

    # 1
    value_1, picks_1 = knapsack_solver_recursion(values=values[1:],
                                                 weights=weights[1:],
                                                 capacity=capacity -
                                                 weights[0])
    total_value_1 = values[0] + value_1
    picks_1 = [1] + picks_1

    # 2
    value_2, picks_2 = knapsack_solver_recursion(values=values[1:],
                                                 weights=weights[1:],
                                                 capacity=capacity)
    total_value_2 = value_2
    picks_2 = [0] + picks_2

    # The largest total value will be chosen.
    if total_value_1 >= total_value_2:
        return total_value_1, picks_1
    else:
        return total_value_2, picks_2


def knapsack_solver_dynamic_programming(
        values: List[Union[int, float]], weights: List[int],
        capacity: int) -> Tuple[Union[int, float], List[bool]]:

    # Time complexity: O(n x c)
    # Space complexity: O(n^2 x c)
    # It is possible to make the space complexity to O(n x c) by only tracking two rows of the DP table..
    # But we will skip the implementation.

    # The idea is somewhat similar to the recursion method.
    # Prepare an (n + 1) x (c + 1) auxiliary DP table v.
    # 1-indexed.
    # v[i][j] is the maximum value for items from 1 to i and capacity j.
    # For each cell [i,j], it also has two scenarios.
    # 1. Item i is in the optimal solution.
    # 2. Item i is not in the optimal solution.

    assert len(values) == len(weights)
    n = len(values)
    c = capacity

    v = [[0] * (c + 1) for _ in range(n + 1)]
    picks = [[0] * (c + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        picks[i][0] = [0 for _ in range(i)]
    for j in range(0, c + 1):
        picks[0][j] = []

    for i in range(1, n + 1):
        for j in range(1, c + 1):
            weight = weights[i - 1]
            value = values[i - 1]

            if j - weight < 0:
                # Item i must not be in the optimal solution
                v[i][j] = v[i - 1][j]
                picks[i][j] = picks[i - 1][j] + [0]
            else:
                v1 = v[i - 1][j]
                v2 = v[i - 1][j - weight] + value
                if v1 >= v2:
                    v[i][j] = v1
                    picks[i][j] = picks[i - 1][j] + [0]
                else:
                    v[i][j] = v2
                    picks[i][j] = picks[i - 1][j - weight] + [1]

    return v[n][c], picks[n][c]


def knapsack_solver_integer_programming(
        values: List[Union[int, float]], weights: List[Union[int, float]],
        capacity: int) -> Tuple[Union[int, float], List[bool]]:

    n = len(values)

    # Knapsack problem is a maximization problem.
    model = LpProblem(name="Knapsack-Problem", sense=LpMaximize)

    # Our variables are 0/1 binary integers.
    # If we have n items, we will have n variables.
    lp_variables = [
        # LpVariable(name=f"x_{i+1}", lowBound=0, upBound=1, cat=LpInteger)
        LpVariable(name=f"x_{i+1}", cat=LpBinary)
        for i in range(n)
    ]

    # Add constraints.
    total_weight_expression = 0
    for lp_variable, weight in zip(lp_variables, weights):
        total_weight_expression += lp_variable * weight
    total_weight_constraint = total_weight_expression <= capacity

    # Add the constraints to the model.
    model += total_weight_constraint

    # Add objectives.
    total_value_expression = 0
    for lp_variable, value in zip(lp_variables, values):
        total_value_expression += lp_variable * value
    # Add the objective function to the model.
    model += total_value_expression

    # print(model)
    status = model.solve(solver=GLPK(msg=False))

    assert status == True, "Linear programming solver did not solve the problem successfully."

    picks = [int(variable.value()) for variable in model.variables()]
    maximum_value = model.objective.value()

    return maximum_value, picks


def test_knapsack_solver(knapsack_solver: Callable) -> bool:

    # All values, weights, and capacity should be > 0.
    weights = [10, 20, 30]
    values = [60, 100, 120]
    capacity = 50

    maximum_total_value, picks = knapsack_solver(values=values,
                                                 weights=weights,
                                                 capacity=capacity)

    if maximum_total_value != 220:
        return False

    weights = [31, 10, 20, 19, 4, 3, 6]
    values = [70, 20, 39, 37, 7, 5, 10]
    capacity = 50

    maximum_total_value, picks = knapsack_solver(values=values,
                                                 weights=weights,
                                                 capacity=capacity)

    if maximum_total_value != 107:
        return False

    weights = [25, 35, 45, 5, 25, 3, 2, 2]
    values = [350, 400, 450, 20, 70, 8, 5, 5]
    capacity = 104

    maximum_total_value, picks = knapsack_solver(values=values,
                                                 weights=weights,
                                                 capacity=capacity)

    if maximum_total_value != 900:
        return False

    return True


def generate_random_knapsack_problem(num_items: int):

    values = list(np.random.uniform(low=1, high=10, size=num_items))
    weights = list(np.random.randint(low=1, high=25, size=num_items))
    capacity = int(np.sum(weights) // 10)

    return values, weights, capacity


def main():

    np.random.seed(seed=0)

    # Some unit tests.
    assert test_knapsack_solver(
        knapsack_solver=knapsack_solver_recursion) == True
    assert test_knapsack_solver(
        knapsack_solver=knapsack_solver_dynamic_programming) == True
    assert test_knapsack_solver(
        knapsack_solver=knapsack_solver_integer_programming) == True

    weights = [2, 1, 2, 1, 1, 5, 1]
    values = [10, 9, 7, 5, 4, 3, 3]
    capacity = 5

    print("-" * 75)
    print("Knapsack Problem: ")
    print("Item Weights:")
    print(weights)
    print("Item Values:")
    print(values)
    print("Weight Capacity:")
    print(capacity)
    print("-" * 75)

    maximum_value, picks = knapsack_solver_dynamic_programming(
        values=values, weights=weights, capacity=capacity)
    print("Dynamic Programming Solution:")
    print("Maximum Value:")
    print(maximum_value)
    print("Picks:")
    print(picks)
    print("-" * 75)

    maximum_value, picks = knapsack_solver_integer_programming(
        values=values, weights=weights, capacity=capacity)
    print("Integer Linear Programming Solution:")
    print("Maximum Value:")
    print(maximum_value)
    print("Picks:")
    print(picks)
    print("-" * 75)

    print("Profiling a Large Knapsack Problem...")
    # Generate a large knapsack problem
    values, weights, capacity = generate_random_knapsack_problem(
        num_items=1000)

    start = timer()
    maximum_value, picks = knapsack_solver_dynamic_programming(
        values=values, weights=weights, capacity=capacity)
    end = timer()
    print(
        f"Dynamic Programming Solver Time Elapsed: {timedelta(seconds=end-start)}"
    )

    start = timer()
    maximum_value, picks = knapsack_solver_integer_programming(
        values=values, weights=weights, capacity=capacity)
    end = timer()
    print(
        f"Integer Linear Programming Solver Time Elapsed: {timedelta(seconds=end-start)}"
    )
    print("-" * 75)


if __name__ == "__main__":

    main()

Knapsack Problem Solver Execution

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

$ python knapsack.py 
---------------------------------------------------------------------------
Knapsack Problem: 
Item Weights:
[2, 1, 2, 1, 1, 5, 1]
Item Values:
[10, 9, 7, 5, 4, 3, 3]
Weight Capacity:
5
---------------------------------------------------------------------------
Dynamic Programming Solution:
Maximum Value:
28
Picks:
[1, 1, 0, 1, 1, 0, 0]
---------------------------------------------------------------------------
Integer Linear Programming Solution:
Maximum Value:
28
Picks:
[1, 1, 0, 1, 1, 0, 0]
---------------------------------------------------------------------------
Profiling a Large Knapsack Problem...
Dynamic Programming Solver Time Elapsed: 0:00:56.873142
Integer Linear Programming Solver Time Elapsed: 0:00:00.555069
---------------------------------------------------------------------------

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.

References

• Knapsack Problem
• Hands-On Linear Programming: Optimization With Python