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.