Combinatorial Optimization with D-Wave Ocean SDK

Solving Knapsack Problem with D-Wave Quantum Annealing

Maximize Value Without Overloading!

Backstory

You’re on a game show where you can win as many prizes as you want — but here’s the catch — they all have to fit into a small knapsack! Each prize has a different size and value, so you must choose the most valuable combination that fits to maximize your winnings.

This challenge of maximizing the total value within a limit is the essence of the knapsack problem:

• We have a set of items, each with a value and a size.
• The objective is to select a subset of these items to maximize the total value while ensuring the total size under a given capacity.

Mathematical Definition

Binary Variables

Let’s define a binary variable xᵢ​ for each item i:

• xᵢ​ = 1 if item i is selected.
• xᵢ = 0 if item i is not selected.

Constants

• vᵢ is the value of item i.
• sᵢ​​​ is the size of item i.
• C is the capacity.