# The knapsack problem

*This file can be downloaded as a jupyter notebook and executed with a Java kernel. The next cell is then used to add the dependency to choco and can be ignored otherwise.*

```
// Add maven dependencies at runtime
%maven org.choco-solver:choco-solver:4.10.13
```

Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most useful items."

First manage imports.

```
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.exception.ContradictionException;
import org.chocosolver.solver.variables.IntVar;
import java.util.Arrays;
import static org.chocosolver.solver.search.strategy.Search.inputOrderLBSearch;
import static org.chocosolver.solver.search.strategy.Search.inputOrderUBSearch;
```

## Input data

```
int n = 10; // number of different items
int W = 67; // a maximum weight capacity
int[] w = new int[]{23, 26,20,18,32, 27, 29, 26, 30, 27}; // weight of items
int[] v = new int[]{505, 352, 458, 220, 354, 414, 498, 545, 473, 543}; // value of items
```

## The model

Then, we can start modelling the problem with choco.
The first step is to defined a `Model`

instance.
It is required to declare and store the variables and the constraints.
For convenience, an instance can be declared with a name.

`Model model = new Model("Knapsack");`

For each object, a variable is declared to count the number of times it appears in the knapsack.

```
IntVar[] items = new IntVar[n];
for (int i = 0; i < n; i++) {
items[i] = model.intVar("item_" + (i + 1), 0, (int) Math.ceil(W*1. / w[i]));
}
```

The paramaters are:

- the prefix for setting the variables’ name,
- the lower bound and the upper bound of each variable.

**Remark:**
*To model 0-1 knapsack problem, the upper bound of each variable must be set to $1$.*

The problem is to maximize the sum of the values of the items in the knapsack. This amount is maintained in a variable:

`IntVar value = model.intVar("value", 0, Arrays.stream(v).max().orElse(999) * n);`

The sum of the weights is less than or equal to the knapsack’s capacity:

`IntVar weight = model.intVar("weight", 0, W);`

All variables are now declared, the `knapsack`

constraint can be declared:

`model.knapsack(items, weight, value, w, v).post();`

The `value`

variable has to be maximized:

`model.setObjective(Model.MAXIMIZE, value);`

## Finding the optimal solution

Now that the model is ready, the solving step can be set up. Here we define a top-down maximization:

```
Solver solver = model.getSolver();
solver.setSearch(
inputOrderUBSearch(value),
inputOrderLBSearch(items));
```

Let’s execute the solving:

```
while (solver.solve()) {
System.out.printf("Knapsack -- %d items\n", n);
System.out.println("\tItem: Count");
for (int i = 0; i < items.length; i++) {
System.out.printf("\tItem #%d: %d\n", (i+1), items[i].getValue());
}
System.out.printf("\n\tWeight: %d\n", weight.getValue());
System.out.printf("\n\tValue: %d\n", value.getValue());
}
solver.reset(); // to solve the model several times
```

```
Knapsack -- 10 items
Item: Count
Item #1: 2
Item #2: 0
Item #3: 1
Item #4: 0
Item #5: 0
Item #6: 0
Item #7: 0
Item #8: 0
Item #9: 0
Item #10: 0
Weight: 66
Value: 1468
```

The optimal value for this instance of the knapsack problem is $1468$ with a total weight of $66$.

When turned to a 0-1 knapsack problem, the optimal value is $1270$ with a total weight of $67$.