107 lines
6.3 KiB
Plaintext
107 lines
6.3 KiB
Plaintext
---
|
||
title: knapsack
|
||
description: API reference for qiskit.optimization.applications.ising.knapsack
|
||
in_page_toc_min_heading_level: 2
|
||
python_api_type: module
|
||
python_api_name: qiskit.optimization.applications.ising.knapsack
|
||
---
|
||
|
||
<span id="module-qiskit.optimization.applications.ising.knapsack" />
|
||
|
||
<span id="qiskit-optimization-applications-ising-knapsack" />
|
||
|
||
# qiskit.optimization.applications.ising.knapsack
|
||
|
||
Convert knapsack parameters instances into Pauli list The parameters are a list of values a list of weights and a maximum weight of the knapsack.
|
||
|
||
In the Knapsack Problem we are given a list of objects that each has a weight and a value. We are also given a maximum weight we can carry. We need to pick a subset of the objects so as to maximize the total value without going over the maximum weight.
|
||
|
||
If we have the weights w\[i], the values v\[i] and the maximum weight W\_max. We express the solution as a binary array x\[i] where we have a 1 for the items we take in the solution set. We need to maximize sum(x\[i]\*v\[i]) while respecting W\_max >= sum(x\[i]\*w\[i])
|
||
|
||
**Functions**
|
||
|
||
| | |
|
||
| ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------ |
|
||
| [`get_operator`](#qiskit.optimization.applications.ising.knapsack.get_operator "qiskit.optimization.applications.ising.knapsack.get_operator")(values, weights, max\_weight) | Generate Hamiltonian for the knapsack problem. |
|
||
| [`get_solution`](#qiskit.optimization.applications.ising.knapsack.get_solution "qiskit.optimization.applications.ising.knapsack.get_solution")(x, values) | Get the solution to the knapsack problem from the bitstring that represents to the ground state of the Hamiltonian |
|
||
| [`knapsack_value_weight`](#qiskit.optimization.applications.ising.knapsack.knapsack_value_weight "qiskit.optimization.applications.ising.knapsack.knapsack_value_weight")(solution, values, weights) | Get the total wight and value of the items taken in the knapsack. |
|
||
|
||
### get\_operator
|
||
|
||
<Function id="qiskit.optimization.applications.ising.knapsack.get_operator" github="https://github.com/qiskit-community/qiskit-aqua/tree/stable/0.8/qiskit/optimization/applications/ising/knapsack.py" signature="get_operator(values, weights, max_weight)">
|
||
Generate Hamiltonian for the knapsack problem.
|
||
|
||
**Notes**
|
||
|
||
To build the cost function for the Hamiltonian we add a term S that will vary with our solution. In order to make it change wit the solution we enhance X with a number of additional bits X’ = \[x\_0,..x\_\{n-1},y\_\{n}..y\_\{n+m-1}]. The bytes y\[i] will be the binary representation of S. In this way the optimizer will be able to optimize S as well as X.
|
||
|
||
The cost function is \$\$C(X’) = M(W\_\{max} - sum\_\{i=0}^\{n-1} x\_\{i}w\_\{i} - S)^2 - sum\_\{i}^\{n-1} x\_\{i}v\_\{i}\$\$ where S = sum(2\*\*j \* y\[j]), j goes from n to n+log(W\_max). M is a number large enough to dominate the sum of values.
|
||
|
||
Because S can only be positive, when W\_max >= sum(x\[i]\*w\[i]) the optimizer can find an S (or better the y\[j] that compose S) so that it will take the first term to 0. This way the function is dominated by the sum of values. If W\_max \< sum(x\[i]\*w\[i]) then the first term can never be 0 and, multiplied by a large M, will always dominate the function.
|
||
|
||
The minimum value of the function will be that where the constraint is respected and the sum of values is maximized.
|
||
|
||
**Parameters**
|
||
|
||
* **values** (*list of non-negative integers*) – a list of values
|
||
* **weights** (*list of non-negative integers*) – a list of weights
|
||
* **max\_weight** (*non negative integer*) – the maximum weight the knapsack can carry
|
||
|
||
**Returns**
|
||
|
||
operator for the Hamiltonian float: a constant shift for the obj function.
|
||
|
||
**Return type**
|
||
|
||
[WeightedPauliOperator](qiskit.aqua.operators.legacy.WeightedPauliOperator "qiskit.aqua.operators.legacy.WeightedPauliOperator")
|
||
|
||
**Raises**
|
||
|
||
* **ValueError** – values and weights have different lengths
|
||
* **ValueError** – A value or a weight is negative
|
||
* **ValueError** – All values are zero
|
||
* **ValueError** – max\_weight is negative
|
||
</Function>
|
||
|
||
### get\_solution
|
||
|
||
<Function id="qiskit.optimization.applications.ising.knapsack.get_solution" github="https://github.com/qiskit-community/qiskit-aqua/tree/stable/0.8/qiskit/optimization/applications/ising/knapsack.py" signature="get_solution(x, values)">
|
||
Get the solution to the knapsack problem from the bitstring that represents to the ground state of the Hamiltonian
|
||
|
||
**Parameters**
|
||
|
||
* **x** (*numpy.ndarray*) – the ground state of the Hamiltonian.
|
||
* **values** (*numpy.ndarray*) – the list of values
|
||
|
||
**Returns**
|
||
|
||
**a bit string that has a ‘1’ at the indexes**
|
||
|
||
corresponding to values that have been taken in the knapsack. i.e. if the solution has a ‘1’ at index i then the value values\[i] has been taken in the knapsack
|
||
|
||
**Return type**
|
||
|
||
numpy.ndarray
|
||
</Function>
|
||
|
||
### knapsack\_value\_weight
|
||
|
||
<Function id="qiskit.optimization.applications.ising.knapsack.knapsack_value_weight" github="https://github.com/qiskit-community/qiskit-aqua/tree/stable/0.8/qiskit/optimization/applications/ising/knapsack.py" signature="knapsack_value_weight(solution, values, weights)">
|
||
Get the total wight and value of the items taken in the knapsack.
|
||
|
||
**Parameters**
|
||
|
||
* **solution** (*numpy.ndarray*) – binary string that represents the solution to the problem.
|
||
* **values** (*numpy.ndarray*) – the list of values
|
||
* **weights** (*numpy.ndarray*) – the list of weights
|
||
|
||
**Returns**
|
||
|
||
the total value and weight of the items in the knapsack
|
||
|
||
**Return type**
|
||
|
||
tuple
|
||
</Function>
|
||
|