Solve the knapsack problem in Python

The knapsack problem shows up whenever you must choose a subset under a budget: pick items to maximize total value without exceeding a weight (or cost, or time) limit. It is the textbook model behind selecting features under an effort budget, ads under a screen limit, or investments under a cash cap. It's also called the 0/1 (binary) knapsack — subset selection under a budget.

The tempting first attempt is to enumerate every subset. The approach that keeps working is to model it and hand it to a solver — with quicopt that is a few lines of Python.

The brute-force trap

"Try every subset" translates directly to a loop over all 0/1 combinations:

from itertools import product

weights  = [2, 3, 4, 5, 9, 7, 1, 6]
values   = [3, 4, 5, 8, 10, 6, 2, 7]
capacity = 15
N = len(weights)

best = 0
for pick in product([0, 1], repeat=N):
    if sum(weights[i] for i in range(N) if pick[i]) <= capacity:
        best = max(best, sum(values[i] for i in range(N) if pick[i]))
print(best)  # -> 22

Correct for eight items. But the number of subsets is 2^N, which doubles with every item added:

• 8 items → 256 subsets (instant)
• 20 items → 1,048,576
• 40 items → 1,099,511,627,776 (over a trillion)

Enumeration collapses long before instances get interesting.

Model it as a MILP

Knapsack is a mixed-integer linear program (MILP). A binary variable x[i] says whether item i is taken. One linear constraint keeps the chosen weight within capacity, and the objective maximizes the chosen value:

from ortools.math_opt.python import mathopt
from quicopt import Client

# 0/1 knapsack: pick items to maximize value without exceeding the weight budget.
weights  = [2, 3, 4, 5, 9, 7, 1, 6]
values   = [3, 4, 5, 8, 10, 6, 2, 7]
capacity = 15
N = len(weights)

model = mathopt.Model(name="knapsack")
x = [model.add_binary_variable(name=f"x_{i}") for i in range(N)]
model.add_linear_constraint(sum(weights[i] * x[i] for i in range(N)) <= capacity)
model.maximize(sum(values[i] * x[i] for i in range(N)))

client = Client("https://try.quicoptapi.pgi.fz-juelich.de")
result = client.solve(model)
print(result.display)

├── status:     optimal
├── feasible:   true
├── objective:  22.0
├── x:          x_0=1, x_1=1, x_2=1, x_3=1, x_4=0, x_5=0, …  (8 variables)
└── solve_time: 0.0104 s

What you get

status: optimal means the solver proved no subset does better — value 22, taking items 0, 1, 2, 3, 6 for a total weight of exactly 15. It matches the brute-force answer and comes back in about a hundredth of a second.

The difference is scaling. Brute force is O(2^n); a MILP solver uses bounds and branch-and-cut to prune the search instead of walking it. The same eight-line model that handles eight items handles eight hundred — you change the data, not the method.

Next

• The problem class behind this: MILP
• Related guides: Set cover · Bin packing
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990.