Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
[scipy 1.9+] milp: Mixed-integer linear programming solution in 3rd party category for Knapsack Problem by Phil15
import numpy as np
from scipy.optimize import Bounds, LinearConstraint, milp
def knapsack(total_weight: int, items: list[tuple[int, int] | tuple[int, int, int]]) -> int:
values, weights, limits = np.array([[v, w, b[0] if b else np.inf] for v, w, *b in items]).T
res = milp(
# "milp" minimizes so to maximize, we need to negate values AND the optimal result "fun".
-values,
integrality=1, # All internal variables will be integers.
# lb/up stand for lower/upper bounds.
bounds=Bounds(lb=0, ub=limits),
constraints=LinearConstraint(weights, lb=0, ub=total_weight),
)
assert res.success
return -res.fun
April 25, 2023
