quboResult2knapsack

Convert QUBO result to knapsack solution

Since R2025b

Syntax

[items,totalValue,totalWeight] = quboResult2knapsack(result,v,w,M)

Description

Add-On Required: This feature requires the MATLAB Support Package for Quantum Computing add-on.

[items,totalValue,totalWeight] = quboResult2knapsack(result,v,w,M) converts the result of solving the knapsack QUBO formulation to a solution for the corresponding problem. Use this function after solving a QUBO formulation created using the knapsack2qubo function.

Examples

Convert Knapsack Problem to QUBO

Define a knapsack problem by creating two 1-by-5 vectors that represent the values and weights of five items. Create a numeric scalar that represents the maximum weight capacity of the knapsack.

v = [5 2 8 4 3];
w = [9 8 4 5 2];
M = 17;

Convert the knapsack problem to a QUBO problem.

qprob = knapsack2qubo(v,w,M)

qprob = 
  qubo with properties:

    QuadraticTerm: [10×10 double]
       LinearTerm: [10×1 double]
     ConstantTerm: 289
     NumVariables: 10

Solve the QUBO problem.

result = solve(qprob)

result = 
  quboResult with properties:

                BestX: [10×1 double]
    BestFunctionValue: -16
      AlgorithmResult: [1×1 tabuSearchResult]

Convert the result of the QUBO problem to the knapsack formulation. The solution to the knapsack problem is to include the first, third, and fifth items in the list. These items have a total value of 16 and a total weight of 15, which is less than the specified maximum weight of 17.

[items,totalValue,totalWeight] = quboResult2knapsack(result,v,w,M)

items = 3×1

     1
     3
     5

totalValue = 
16

totalWeight = 
15

Input Arguments

result — Solution of knapsack QUBO problem

quboResult object

Solution of the knapsack QUBO problem, specified as a quboResult object. Create result using the solve function for a QUBO problem generated using knapsack2qubo.

v — Item values

numeric vector

Item values, specified as a numeric vector. Each element of v corresponds to the value of an item that can be placed in the knapsack. For example, the first item of those that can be placed in the knapsack has value v(1).

Data Types: double

w — Item weights

numeric vector

Item weights, specified as a numeric vector. Each element of w corresponds to the weight of an item that can be placed in the knapsack. For example, the first item of those that can be placed in the knapsack has weight w(1).

Data Types: double

M — Maximum weight capacity of knapsack

numeric scalar

Maximum weight capacity of the knapsack, specified as a numeric scalar.

Data Types: double

Output Arguments

items — Items selected

numeric vector

Items selected, returned as a numeric vector. Each element of items corresponds to the index of an item from the original knapsack problem.

Data Types: double

totalValue — Total value of all items selected

positive numeric scalar

Total value of all items selected, returned as a positive numeric scalar.

Data Types: double

totalWeight — Total weight of all items selected

positive numeric scalar

Total weight of all items selected, returned as a positive numeric scalar.

Data Types: double

More About

Knapsack Problem

The classic knapsack problem involves a knapsack with a maximum weight capacity that a person must fill with items of varying value and weight. The problem is to maximize the value of the items in the knapsack without exceeding the maximum weight capacity. Each item can be selected only once.

Version History

Introduced in R2025b