dwave.optimization.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) Model[source]#

Generate a model encoding a knapsack problem.

The knapsack problem is, for a given set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Parameters:
  • values – A 1D array-like (row vector or Python list) of values per item. The length of values must be equal to the length of weights. Values can be any non-negative number.

  • weights – A 1D array-like (row vector or Python list) of weights per item. Weights can be any non-negative number.

  • capacity – Maximum capacity of the knapsack. Must be a positive number.

Returns:

A model encoding the knapsack problem.

The model generated uses a dwave.optimization.Model.set class as the decision variable being optimized, with permutations of subsets of this set representing possible items included in the knapsack.