dimod.generators.quadratic_knapsack#

quadratic_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], profits: _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 quadratic knapsack problem.

The quadratic knapsack problem, QKP, 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.

  • profits – A matrix where entry (i, j) is the value of adding items i and j together.

  • capacity – The maximum weight a knapsack can hold.

Returns:

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