Lesson 2

The knapsack problem is formulated in terms of integer linear programming simply and naturally. For each item, we introduce a 0/1-variable: it equals one if we put this item into the knapsack, and zero otherwise. In terms of these variables, we have just one inequality: the sum of weights of the selected items must not exceed the capacity of the knapsack. And we maximize the sum of the values of the selected items.

from mip import *


def knapsack(capacity, weights):
    model = Model(solver_name='cbc')
    model.verbose = False

    variables = [model.add_var(var_type=BINARY) for _ in range(len(weights))]

    model += xsum(weights[i] * variables[i] for i in range(len(weights))) <= capacity
    model.objective = maximize(xsum(weights[i] * variables[i] for i in range(len(weights))))
    model.optimize()

    return int(model.objective_value)


print(knapsack(capacity=28, weights=[17, 9, 7, 3]))
print(knapsack(capacity=300, weights=[2] * 100))

27
200