# Knapsacks

## Overview

The goal of the knapsack problem is to pack a set of items, with given sizes and values, into a container with a fixed capacity, so as to maximize the total value of the packed items. In this section you'll learn how to use OR-Tools to solve the knapsack problem.

## Example

Here's a graphical depiction of a knapsack problem:

In the above animation, 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.

The following sections describe programs that solve a knapsack problem.

### Create the data

The code below creates the data for the problem.

### Python

```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]```

### C++

```std::vector<int64> 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};

std::vector<std::vector<int64>> 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}};

std::vector<int64> capacities = {850};```

### Java

```final long[] 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};

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};```

### C#

```long[] 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 };

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 } };

long[] capacities = { 850 };```

The data includes the following:

• `weights`: A vector containing the weights of the items.
• `values`: A vector containing the values of the items.
• `capacities`: A vector with just one entry, the capacity of the knapsack.

### Declare the solver

The following code declares the knapsack solver, a specialized solver for knapsack problems.

### Python

```solver = pywrapknapsack_solver.KnapsackSolver(
pywrapknapsack_solver.KnapsackSolver.
KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, 'KnapsackExample')```

### C++

```KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");```

### Java

```KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");```

### C#

```KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");```

The option `KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER` tells the solver to use the brand and bound algorithm to solve the problem.

### Call the solver

The following code calls the solver and prints the output.

### Python

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

### C++

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

### Java

```solver.init(values, weights, capacities);
final long computedValue = solver.solve();```

### C#

```solver.Init(values, weights, capacities);
long computedValue = solver.Solve();```

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.

```Total value = 7534
Total weight: 850
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]
```

### Complete programs

Below are the complete programs that solve the knapsack problem.

### Python

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

def main():
# Create the solver.
solver = pywrapknapsack_solver.KnapsackSolver(
pywrapknapsack_solver.KnapsackSolver.
KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, 'KnapsackExample')

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 = []
packed_weights = []
total_weight = 0
print('Total value =', computed_value)
for i in range(len(values)):
if solver.BestSolutionContains(i):
packed_items.append(i)
packed_weights.append(weights[0][i])
total_weight += weights[0][i]
print('Total weight:', total_weight)
print('Packed items:', packed_items)
print('Packed_weights:', packed_weights)

if __name__ == '__main__':
main()```

### C++

```#include <iterator>
#include <numeric>
#include <sstream>

#include "ortools/algorithms/knapsack_solver.h"

namespace operations_research {
void RunKnapsackExample() {
// Instantiate the solver.
KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");

std::vector<int64> 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};

std::vector<std::vector<int64>> 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}};

std::vector<int64> capacities = {850};

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

// Print solution
std::vector<int> packed_items;
for (std::size_t i = 0; i < values.size(); ++i) {
if (solver.BestSolutionContains(i)) packed_items.push_back(i);
}
std::ostringstream packed_items_ss;
std::copy(packed_items.begin(), packed_items.end() - 1,
std::ostream_iterator<int>(packed_items_ss, ", "));
packed_items_ss << packed_items.back();

std::vector<int64> packed_weights;
packed_weights.reserve(packed_items.size());
for (const auto &it : packed_items) {
packed_weights.push_back(weights[0][it]);
}
std::ostringstream packed_weights_ss;
std::copy(packed_weights.begin(), packed_weights.end() - 1,
std::ostream_iterator<int>(packed_weights_ss, ", "));
packed_weights_ss << packed_weights.back();

int64 total_weights =
std::accumulate(packed_weights.begin(), packed_weights.end(), 0LL);

LOG(INFO) << "Total value: " << computed_value;
LOG(INFO) << "Packed items: {" << packed_items_ss.str() << "}";
LOG(INFO) << "Total weight: " << total_weights;
LOG(INFO) << "Packed weights: {" << packed_weights_ss.str() << "}";
}
}  // namespace operations_research

int main(int argc, char **argv) {
operations_research::RunKnapsackExample();
return EXIT_SUCCESS;
}```

### Java

```import com.google.ortools.algorithms.KnapsackSolver;
import java.util.ArrayList;

/**
* Sample showing how to model using the knapsack solver.
*
*/
public class Knapsack {
static {
}

private static void solve() {
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");

final long[] 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};

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(values, weights, capacities);
final long computedValue = solver.solve();

ArrayList<Integer> packedItems = new ArrayList<Integer>();
ArrayList<Long> packedWeights = new ArrayList<Long>();
int totalWeight = 0;
System.out.println("Total value = " + computedValue);
for (int i = 0; i < values.length; i++) {
if (solver.bestSolutionContains(i)) {
totalWeight = (int) (totalWeight + weights[0][i]);
}
}
System.out.println("Total weight: " + totalWeight);
System.out.println("Packed items: " + packedItems);
System.out.println("Packed weights: " + packedWeights);
}

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

### C#

```using System;

public class Knapsack
{
static void Main()
{
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");

long[] 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 };

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 } };

long[] capacities = { 850 };

solver.Init(values, weights, capacities);
long computedValue = solver.Solve();

Console.WriteLine("Optimal Value = " + computedValue);
}
}```