# Knapsacks

## Overview

A knapsack is a bin-packing problem, in which the goal is to maximize the total value of items in (typically) a single bin. In this documentation you'll learn how to use OR-Tools to solve knapsack problems.

## A simple example

Here's a graphical depiction of a knapsack problem:

In the above figure, 50 items are packed into a bin. Each item has a value (the number on the item) and a weight (roughly proportional to the area of the item). The bin is declared to have a capacity of 850, and our goal is to find the set of items that will maximize the total value without exceeding the capacity.

We'll demonstrate how to compute solutions with the Python and Java interfaces to OR-Tools.

Whatever language you use, the process is the same:

• Create an instance of `KnapsackSolver`.
• Declare the values, weights, and capacities.
• Initialize the solver with that data.
• Call the `Solve()` method.
• Display the result.

Before solving this problem, we'll show how to solve an even simpler knapsack problem, in which the value of each object equals its weight. In this case, the problem is simply to pack the bin with items whose total weight is as large as possible. The following sections describe a Python program that solves this problem.

### Data for the problem

The code below creates the data for the problem.

```  weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
125, 670, 892, 600, 293, 712, 147, 421, 255]]
capacities = [850]
values = weights[0]```

The vector `weights` contains the weights of the items. The vector `capacities` has just one entry, `850`, which is the capacity of the knapsack. (In problems with multiple bins, each entry of `capacities` contains the capacity of the corresponding bin.) The solver also requires a vector of `values`, which is the same `weights` in this case.

### Creating the solver

The following code creates the solver for the problem.

```from ortools.algorithms import pywrapknapsack_solver

def main():
# Create the solver.
solver = pywrapknapsack_solver.KnapsackSolver(
pywrapknapsack_solver.KnapsackSolver.
KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
'test')
```

The program uses the knapsack dynamic programming solver — a specialized solver for the knapsack problem. To create an instance of the solver, the program imports `pywrapknapsack_solver`, a Python wrapper for the C++ solver, `KnapsackSolver`, and then calls `pywrapknapsack_solver` with the `KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER` option.

Note: `KnapsackSolver` only accepts integer values for the weights and values. However, Using a solver with non-integer data shows how to use the solver if your data contains non-integer values.

While you can solve the knapsack problem with other OR-Tools solvers, such as the mixed integer programming solver, the knapsack dynamic programming solver can solve it faster.

### Invoking the solver

The following code invokes the solver and prints the output.

```  solver.Init(values, weights, capacities)
computed_value = solver.Solve()

packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]
packed_weights = [weights[0][i] for i in packed_items]

print("Packed items: ", packed_items)
print("Packed weights: ", packed_weights)
print("Total weight (same as total value): ", computed_value)```

The program first initializes the solver, and then calls it by `computed_value = solver.Solve()`. The total value of the optimal solution is `computed_value`, which is the same as the total weight in this case. The program then gets the indices of the packed items in the solution by the following command:

```packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]```
Since `solver.BestSolutionContains(x)` returns `TRUE` if the item x is included in the solution, `packed_items` is a list of the optimal packed items. Similarly, `packed_weights` are the weights of the packed items.

### Output of the program

Here is the output of the program.

```\$ python my_projects/one_dim_knapsack.py
Packed items:  [2, 3, 6, 13]
Packed weights:  [194, 130, 230, 293]
Total weight (same as total value):  847```

### Using a solver with non-integer data

If your problem involves non-integer data, you can still use the knapsack solver (or any other solver that only accepts integer inputs) as follows. Before invoking the solver, multiply all the data (including the capacities) by a suitably large integer and then round. For instance, if your weights are 3.14159 and 2.71828, multiply by 10000 to make them 314159 and 271828. Then solve and divide the packed weights in the solution by the same number.

### The entire program

The entire program to solve the knapsack problem is shown below.

```from __future__ import print_function
from ortools.algorithms import pywrapknapsack_solver

def main():
# Create the solver.
solver = pywrapknapsack_solver.KnapsackSolver(
pywrapknapsack_solver.KnapsackSolver.
KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
'test')

weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
125, 670, 892, 600, 293, 712, 147, 421, 255]]
capacities = [850]
values = weights[0]
solver.Init(values, weights, capacities)
computed_value = solver.Solve()

packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]
packed_weights = [weights[0][i] for i in packed_items]

print("Packed items: ", packed_items)
print("Packed weights: ", packed_weights)
print("Total weight (same as total value): ", computed_value)
if __name__ == '__main__':
main()```

## Back to the original problem

Next, we show how to solve the original problem given above, in which the values of the items are different from their. weights. The constraint is the same as before — the total weight of packed items cannot exceed the knapsack's capacity. But the goal now is to maximize the total value of the packed items, rather than the total weight.

The following code shows the essential differences between solving this problem as opposed to the previous one.

```  values = [360, 83, 59, 130, 431, 67, 230, 52, 93,
125, 670, 892, 600, 38, 48, 147, 78, 256,
63, 17, 120, 164, 432, 35, 92, 110, 22,
42, 50, 323, 514, 28, 87, 73, 78, 15,
26, 78, 210, 36, 85, 189, 274, 43, 33,
10, 19, 389, 276, 312]

weights = [[7, 0, 30, 22, 80, 94, 11, 81, 70,
64, 59, 18, 0, 36, 3, 8, 15, 42,
9, 0, 42, 47, 52, 32, 26, 48, 55,
6, 29, 84, 2, 4, 18, 56, 7, 29,
93, 44, 71, 3, 86, 66, 31, 65, 0,
79, 20, 65, 52, 13]]

capacities = [850]

solver.Init(values, weights, capacities)
computed_value = solver.Solve()

packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]
packed_weights = [weights[0][i] for i in packed_items]
total_weight= sum(packed_weights)
print "Packed items: ", packed_items
print "Packed weights: ", packed_weights
print "Total value: ", computed_value
print "Total weight: ", total_weight```

Note that `values` is now different from `weights`. In the output, we display the packed items, along with their total value and total weight.

```Packed items:  [0, 1, 3, 4, 6, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21, 22, 24, 27, 28, 29, 30,
31, 32, 34, 38, 39, 41, 42, 44, 47, 48, 49]
Packed weights:  [7, 0, 22, 80, 11, 59, 18, 0, 3, 8, 15, 42, 9, 0, 47, 52, 26, 6, 29, 84, 2, 4,
18, 7, 71, 3, 66, 31, 0, 65, 52, 13]
Total value:  7534
Total weight:  850```

### Complete Python and Java programs

Below are complete Python and Java programs that solve the original knapsack program.

Python
```from ortools.algorithms import pywrapknapsack_solver

def main():
# Create the solver.
solver = pywrapknapsack_solver.KnapsackSolver(
pywrapknapsack_solver.KnapsackSolver.
KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
'test')
values = [360, 83, 59, 130, 431, 67, 230, 52, 93,
125, 670, 892, 600, 38, 48, 147, 78, 256,
63, 17, 120, 164, 432, 35, 92, 110, 22,
42, 50, 323, 514, 28, 87, 73, 78, 15,
26, 78, 210, 36, 85, 189, 274, 43, 33,
10, 19, 389, 276, 312]

weights = [[7, 0, 30, 22, 80, 94, 11, 81, 70,
64, 59, 18, 0, 36, 3, 8, 15, 42,
9, 0, 42, 47, 52, 32, 26, 48, 55,
6, 29, 84, 2, 4, 18, 56, 7, 29,
93, 44, 71, 3, 86, 66, 31, 65, 0,
79, 20, 65, 52, 13]]

capacities = [850]

solver.Init(values, weights, capacities)
computed_value = solver.Solve()

packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]
packed_weights = [weights[0][i] for i in packed_items]
total_weight= sum(packed_weights)
print "Packed items: ", packed_items
print "Packed weights: ", packed_weights
print "Total value: ", computed_value
print "Total weight: ", total_weight
if __name__ == '__main__':
main()
```
Java
```package com.google.ortools.samples;

public class Knapsack {

static {
}

private static void solve() {
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");
final long[] profits = {360, 83, 59, 130, 431, 67, 230, 52, 93,
125, 670, 892, 600, 38, 48, 147, 78, 256,
63, 17, 120, 164, 432, 35, 92, 110, 22,
42, 50, 323, 514, 28, 87, 73, 78, 15,
26, 78, 210, 36, 85, 189, 274, 43, 33,
10, 19, 389, 276, 312};

final long[][] weights = {{7, 0, 30, 22, 80, 94, 11, 81, 70,
64, 59, 18, 0, 36, 3, 8, 15, 42,
9, 0, 42, 47, 52, 32, 26, 48, 55,
6, 29, 84, 2, 4, 18, 56, 7, 29,
93, 44, 71, 3, 86, 66, 31, 65, 0,
79, 20, 65, 52, 13}};

final long[] capacities = {850};

solver.init(profits, weights, capacities);
final long computedWeight = solver.solve();
}

public static void main(String[] args) throws Exception {
Knapsack.solve();
}
}```