dimod.generators.multi_knapsack#

multi_knapsack(values: Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | complex | bytes | str | _NestedSequence[complex | bytes | str], weights: Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | complex | bytes | str | _NestedSequence[complex | bytes | str], capacities: Buffer | _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | complex | bytes | str | _NestedSequence[complex | bytes | str]) → ConstrainedQuadraticModel[source]#

Generate a constrained quadratic model encoding a multiple knapsack problem.

The multiple knapsack problem seeks to fit the most value into each knapsack of weight less than or equal to each knapsack’s 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.

  • capacities – A list of the maximum weights each knapsack can hold.

Returns:

A constrained quadratic model encoding the multiple-knapsack problem. Variables are labelled as x_{i}_{j}, where x_{i}_{j} == 1 means that item i is placed in knapsack j.