# Knapsack

from typing import List, Optional

import numpy as np
import pyomo.core as pyo

def knapsack(
values: List[int],
upper_bound: int,
weights: Optional[List[int]] = None,
max_weight: Optional[int] = None,
) -> pyo.ConcreteModel:
model = pyo.ConcreteModel()

model.x = pyo.Var(
range(len(values)), domain=pyo.NonNegativeIntegers, bounds=(0, upper_bound)
)

if max_weight is not None and weights is not None:
assert len(values) == len(
weights
), "values and weights must be with the same length"
model.weight_constraint = pyo.Constraint(
expr=weights @ np.array(model.x.values()) <= max_weight
)

model.cost = pyo.Objective(
expr=values @ np.array(model.x.values()), sense=pyo.maximize
)

return model


This function generates a PYOMO model that formulates the Knapsack problem. Given a set of items, determine how many items to put in the knapsack to maximize their summed value. The model consists of:

• Integer variable declaration for each node (model.x) indicating how many variables to include.
• Objective rule – a weighted sum of the chosen items.
• Constraint - the total weight of the items is less or equal to the max weight allowed.