The Knapsack Problem

Prerequisites

• Please look at Getting Started first for the most basic functions and the setup of OPTANO.Modeling

The mathematical Model

Sets: \begin{array}{l} U = \text{the set containing }n\text{ items} \newline K \subset U = \text{subsets of }U\text{ containing }i\text{ items} \end{array}

Parameters: \begin{array}{l} v_i = \text{value of item }i\newline w_i = \text{weight of item }i\newline W = \text{maximum weight} \end{array}

Variables: $$y_i = \begin{cases} 1, \text{ if you pick item } i \newline 0, \text{ else} \end{cases}$$

Objective: $$max \sum\limits_{i=1}^n v_i y_i$$

Restrictions:

$$\sum\limits_{i=1}^n w_{i} y_i \le W \qquad \forall i=1,...,n \qquad \text{(Weight constraint)}$$

The Knapsack Problem

• Step 1: Create Business objects for your Model
• Step 2: Create your Model Class
• Step 3: Retrieve the Solution of your Model