Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
mixed integer linear programming solution in 3rd party category for Knapsack Problem by juestr
import numpy as np
from scipy import optimize
def knapsack(weight: int, items: list[tuple[int, int] | tuple[int, int, int]]) -> int:
items = [item + (np.inf,) if len(item) < 3 else item for item in items]
values, weights, supply = np.array(items).T
result = optimize.milp(
c=-values,
constraints=optimize.LinearConstraint(A=weights, lb=0, ub=weight),
integrality=np.full_like(values, True),
bounds=optimize.Bounds(lb=0, ub=supply))
return -result.fun
April 25, 2023
Comments:
