The Knapsack Problem

Overview

In the knapsack problem, you need to pack a set of items, with given values and sizes (such as weights or volumes), into a container with a maximum capacity. If the total size of the items exceeds the capacity, you can't pack them all. In that case, the problem is to choose a subset of the items of maximum total value that will fit in the container.

The following sections show how to solve a knapsack problem using OR-Tools.

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 solution.

Python

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)

C++

solver.Init(values, weights, capacities);
int64 computed_value = solver.Solve();
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() << "}";

Java

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)) {
    packedItems.add(i);
    packedWeights.add(weights[0][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);

C#

solver.Init(values, weights, capacities);
long computedValue = solver.Solve();
Console.WriteLine("Optimal Value = " + computedValue);

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 as follows:

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 {
    System.loadLibrary("jniortools");
  }

  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)) {
        packedItems.add(i);
        packedWeights.add(weights[0][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;
using Google.OrTools.Algorithms;

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