dimod.generators.knapsack#

knapsack(values: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes], weights: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes], capacity: float) → ConstrainedQuadraticModel[source]#

Generates a constrained quadratic model encoding a knapsack problem.

The knapsack problem, KP, seeks to fit the most value into a knapsack of weight less than or equal to capacity for a given list of items with associated values and weights.

Parameters:

  • values – A list of each item’s value.

  • weights – A list of each item’s associated weight.

  • capacity – The maximum weight a knapsack can hold.

Returns:

The quadratic model encoding the knapsack problem. Variables are denoted as x_{i} where x_{i} == 1 means that item i is placed in the knapsack.