DEV Community

derek singh
derek singh

Posted on Originally published at proven-decisions.ai

0-1 knapsack problem: the most valuable set of items that fits (Python notebook)

This is one of 48 free optimization notebooks: the problem, the model with a note on every line, Python code and its real
output. You can open it in Google Colab and press Run, with nothing to install.

The problem

Five items have values 10, 13, 7, 8, 5 and weights 5, 6, 3, 4, 2. The knapsack holds weight 10. Which items maximize total value? Let t1, ..., t5 be 1 if item 1, ..., 5 is taken and 0 if not.

The model

Each line ends with a plain-language note (after #).

maximize 10*t1 + 13*t2 + 7*t3 + 8*t4 + 5*t5
subject to
5*t1 + 6*t2 + 3*t3 + 4*t4 + 2*t5 <= 10
binary: t1, t2, t3, t4, t5
# t1 = 1 if item 1 is taken, 0 otherwise (decision)
# t2 = 1 if item 2 is taken, 0 otherwise (decision)
# t3 = 1 if item 3 is taken, 0 otherwise (decision)
# t4 = 1 if item 4 is taken, 0 otherwise (decision)
# t5 = 1 if item 5 is taken, 0 otherwise (decision)
# objective = total value of the items in the knapsack (value units)
Enter fullscreen mode Exit fullscreen mode

The code (cvxpy)

import cvxpy as cp

t1 = cp.Variable(name='t1', boolean=True)  # 1 if item 1 is taken, 0 otherwise (decision)
t2 = cp.Variable(name='t2', boolean=True)  # 1 if item 2 is taken, 0 otherwise (decision)
t3 = cp.Variable(name='t3', boolean=True)  # 1 if item 3 is taken, 0 otherwise (decision)
t4 = cp.Variable(name='t4', boolean=True)  # 1 if item 4 is taken, 0 otherwise (decision)
t5 = cp.Variable(name='t5', boolean=True)  # 1 if item 5 is taken, 0 otherwise (decision)

objective = cp.Maximize(10*t1 + 13*t2 + 7*t3 + 8*t4 + 5*t5)
constraints = [
    5*t1 + 6*t2 + 3*t3 + 4*t4 + 2*t5 <= 10,
]
problem = cp.Problem(objective, constraints)
problem.solve(solver='HIGHS')
print(problem.status, problem.value)
print('t1 =', t1.value)
print('t2 =', t2.value)
print('t3 =', t3.value)
print('t4 =', t4.value)
print('t5 =', t5.value)
Enter fullscreen mode Exit fullscreen mode

Output, from running exactly this code:

optimal 22.0
t1 = 1.0
t2 = 0.0
t3 = 1.0
t4 = 0.0
t5 = 1.0
Enter fullscreen mode Exit fullscreen mode

The checked answer

The largest objective value is 22, at t1 = 1, t2 = 0, t3 = 1, t4 = 0, t5 = 1. The constraint is satisfied (violation ≤0e+00). Optimal within gap tolerance.

Problem class: ILP; solver: HIGHS.

Run it yourself


This article was written with AI assistance, from a template: every number in it is the solver's, from the run shown above.

Top comments (0)