Multiple Knapsacks

This section shows how to solve the knapsack problem for multiple knapsacks. In this case, it's common to refer to the containers as bins, rather than knapsacks.

The next example shows how to find the optimal way to pack items into five bins.

Example

As in the previous example, you start with a collection of items of varying weights and values. The problem is to pack a subset of the items into five bins, each of which has a maximum capacity of 100, so that the total packed value is a maximum.

The following sections present programs that solve this problem. For the full programs, see Complete programs.

Import the libraries

The code below imports the required libraries.

Python

from __future__ import print_function
from ortools.linear_solver import pywraplp

C++

#include <iostream>
#include <numeric>
#include <vector>

#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

C#

using System;
using Google.OrTools.LinearSolver;

Create the data

The code below creates the data for the example.

Python

def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    data['weights'] = weights
    data['values'] = values
    data['items'] = list(range(len(weights)))
    data['num_items'] = len(weights)
    num_bins = 5
    data['bins'] = list(range(num_bins))
    data['bin_capacities'] = [100, 100, 100, 100, 100]
    return data

C++

struct DataModel {
  const std::vector<int> weights = {48, 30, 42, 36, 36, 48, 42, 42,
                                    36, 24, 30, 30, 42, 36, 36};
  const std::vector<int> values = {10, 30, 25, 50, 35, 30, 15, 40,
                                   30, 35, 45, 10, 20, 30, 25};
  const int num_items = weights.size();
  const int total_value = std::accumulate(values.begin(), values.end(), 0);
  const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
  const int num_bins = 5;
};

Java

static class DataModel {
  public final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
  public final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
  public final int numItems = weights.length;
  public final int numBins = 5;
  public final double[] binCapacities = {100, 100, 100, 100, 100};
}

C#

class DataModel
{
  public static double[] Weights =
    {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
  public static double[] Values =
    {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
  public double[] BinCapacities = {100, 100, 100, 100, 100};
  public int NumItems = Weights.Length;
  public int NumBins = 5;
}

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 containing the capacities of the bins.

In this example, all the bins have the same capacity, but that need not be true in general.

Declare the solver

The example uses the mixed integer programming solver. The following code declares the solver.

Python

  # Create the mip solver with the SCIP backend.
  solver = pywraplp.Solver.CreateSolver('SCIP')
     

C++

  // Create the mip solver with the CBC backend.
  MPSolver solver("multiple_knapsack_mip",
                  MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);
     

Java

  // Create the linear solver with the SCIP backend.
  MPSolver solver = MPSolver.createSolver("SCIP");
  if (solver == null) {
    System.out.println("Could not create solver SCIP");
    return;
  }
      

C#

  // Create the linear solver with the SCIP backend.
  Solver solver = Solver.CreateSolver("SCIP");
      

Create the variables

The following code creates the variables for the problem.

Python

# Variables
# x[i, j] = 1 if item i is packed in bin j.
x = {}
for i in data['items']:
    for j in data['bins']:
        x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

C++

std::vector<std::vector<const MPVariable*>> x(
    data.num_items, std::vector<const MPVariable*>(data.num_bins));
for (int i = 0; i < data.num_items; ++i) {
  for (int j = 0; j < data.num_bins; ++j) {
    x[i][j] = solver.MakeIntVar(0.0, 1.0, "");
  }
}

Java

MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
for (int i = 0; i < data.numItems; ++i) {
  for (int j = 0; j < data.numBins; ++j) {
    x[i][j] = solver.makeIntVar(0, 1, "");
  }
}

C#

Variable[,] x = new Variable[data.NumItems, data.NumBins];
for (int i = 0; i < data.NumItems; i++)
{
  for (int j = 0; j < data.NumBins; j++)
  {
    x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
  }
}

Each x[(i, j)] is a 0-1 variable, where i is an item and j is a bin. In the solution, x[(i, j)] will be 1 if item i is placed in bin j, and 0 otherwise.

Define the constraints

The following code defines the constraints for the problem:

Python

# Constraints
# Each item can be in at most one bin.
for i in data['items']:
    solver.Add(sum(x[i, j] for j in data['bins']) <= 1)
# The amount packed in each bin cannot exceed its capacity.
for j in data['bins']:
    solver.Add(
        sum(x[(i, j)] * data['weights'][i]
            for i in data['items']) <= data['bin_capacities'][j])

C++

// Create the constraints.
// Each item is in at most one bin.
for (int i = 0; i < data.num_items; ++i) {
  LinearExpr sum;
  for (int j = 0; j < data.num_bins; ++j) {
    sum += x[i][j];
  }
  solver.MakeRowConstraint(sum <= 1.0);
}
// For each bin that is used, the total packed weight can be at most
// the bin capacity.
for (int j = 0; j < data.num_bins; ++j) {
  LinearExpr weight;
  for (int i = 0; i < data.num_items; ++i) {
    weight += data.weights[i] * LinearExpr(x[i][j]);
  }
  solver.MakeRowConstraint(weight <= data.bin_capacities[j]);
}

Java

for (int i = 0; i < data.numItems; ++i) {
  MPConstraint constraint = solver.makeConstraint(0, 1, "");
  for (int j = 0; j < data.numBins; ++j) {
    constraint.setCoefficient(x[i][j], 1);
  }
}
for (int j = 0; j < data.numBins; ++j) {
  MPConstraint constraint = solver.makeConstraint(0, data.binCapacities[j], "");
  for (int i = 0; i < data.numItems; ++i) {
    constraint.setCoefficient(x[i][j], data.weights[i]);
  }
}

C#

for (int i = 0; i < data.NumItems; ++i) {
  Constraint constraint = solver.MakeConstraint(0, 1, "");
  for (int j = 0; j < data.NumBins; ++j) {
    constraint.SetCoefficient(x[i, j], 1);
  }
}

for (int j = 0; j < data.NumBins; ++j)
{
  Constraint constraint = solver.MakeConstraint(0, data.BinCapacities[j], "");
  for (int i = 0; i < data.NumItems; ++i)
  {
    constraint.SetCoefficient(x[i, j], DataModel.Weights[i]);
  }
}

The constraints are the following:

  • Each item can be placed in at most one bin. This constraint is set by requiring the sum of x[i][j] over all bins j to be less than or equal to 1.
  • The total weight packed in each bin can't exceed its capacity. This constraint is set by requiring the sum of the weights of items placed in bin j to be less than or equal to the capacity of the bin.

Define the objective

The following code defines the objective function for the problem, which is the total value of the packed items.

Python

# Objective
objective = solver.Objective()

for i in data['items']:
    for j in data['bins']:
        objective.SetCoefficient(x[(i, j)], data['values'][i])
objective.SetMaximization()

C++

// Create the objective function.
MPObjective* const objective = solver.MutableObjective();
LinearExpr value;
for (int i = 0; i < data.num_items; ++i) {
  for (int j = 0; j < data.num_bins; ++j) {
    value += data.values[i] * LinearExpr(x[i][j]);
  }
}
objective->MaximizeLinearExpr(value);

Java

MPObjective objective = solver.objective();
for (int i = 0; i < data.numItems; ++i) {
  for (int j = 0; j < data.numBins; ++j) {
    objective.setCoefficient(x[i][j], data.values[i]);
  }
}
objective.setMaximization();

C#

Objective objective = solver.Objective();
for (int i = 0; i < data.NumItems; ++i)
{
  for (int j = 0; j < data.NumBins; ++j)
  {
    objective.SetCoefficient(x[i, j], DataModel.Values[i]);
  }
}
objective.SetMaximization();

Note that x(i, j)] * data['values'[i] adds the value of item i to the objective if the item is placed in bin j. If i is not placed in any bin, its value doesn't contribute to the objective.

Call the solver and print the solution

The following code calls the solver and prints the solution.

Python

status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print('Total packed value:', objective.Value())
    total_weight = 0
    for j in data['bins']:
        bin_weight = 0
        bin_value = 0
        print('Bin ', j, '\n')
        for i in data['items']:
            if x[i, j].solution_value() > 0:
                print('Item', i, '- weight:', data['weights'][i], ' value:',
                      data['values'][i])
                bin_weight += data['weights'][i]
                bin_value += data['values'][i]
        print('Packed bin weight:', bin_weight)
        print('Packed bin value:', bin_value)
        print()
        total_weight += bin_weight
    print('Total packed weight:', total_weight)
else:
    print('The problem does not have an optimal solution.')

C++

const MPSolver::ResultStatus result_status = solver.Solve();
// Check that the problem has an optimal solution.
if (result_status != MPSolver::OPTIMAL) {
  std::cerr << "The problem does not have an optimal solution!";
}
std::cout << "Total packed value: " << objective->Value() << "\n\n";
double total_weight = 0;
for (int j = 0; j < data.num_bins; ++j) {
  double bin_weight = 0;
  double bin_value = 0;
  std::cout << "Bin " << j << std::endl << std::endl;
  for (int i = 0; i < data.num_items; ++i) {
    if (x[i][j]->solution_value() == 1) {
      std::cout << "Item " << i << " - weight: " << data.weights[i]
                << "  value: " << data.values[i] << std::endl;
      bin_weight += data.weights[i];
      bin_value += data.values[i];
    }
  }
  std::cout << "Packed bin weight: " << bin_weight << std::endl;
  std::cout << "Packed bin value: " << bin_value << std::endl << std::endl;
  total_weight += bin_weight;
}
std::cout << "Total packed weight: " << total_weight << std::endl;

Java

final MPSolver.ResultStatus resultStatus = solver.solve();
// Check that the problem has an optimal solution.
if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
  System.out.println("Total packed value: " + objective.value() + "\n");
  double totalWeight = 0;
  for (int j = 0; j < data.numBins; ++j) {
    double binWeight = 0;
    double binValue = 0;
    System.out.println("Bin " + j + "\n");
    for (int i = 0; i < data.numItems; ++i) {
      if (x[i][j].solutionValue() == 1) {
        System.out.println(
            "Item " + i + " - weight: " + data.weights[i] + "  value: " + data.values[i]);
        binWeight += data.weights[i];
        binValue += data.values[i];
      }
    }
    System.out.println("Packed bin weight: " + binWeight);
    System.out.println("Packed bin value: " + binValue + "\n");
    totalWeight += binWeight;
  }
  System.out.println("Total packed weight: " + totalWeight);
} else {
  System.err.println("The problem does not have an optimal solution.");
}

C#

Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus != Solver.ResultStatus.OPTIMAL)
{
  Console.WriteLine("The problem does not have an optimal solution!");
  return;
}
Console.WriteLine("Total packed value: " + solver.Objective().Value());
double TotalWeight = 0.0;
for (int j = 0; j < data.NumBins; ++j)
{
  double BinWeight = 0.0;
  double BinValue = 0.0;
  Console.WriteLine("Bin " + j);
  for (int i = 0; i < data.NumItems; ++i)
  {
    if (x[i, j].SolutionValue() == 1)
    {
      Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]} values: {DataModel.Values[i]}");
      BinWeight += DataModel.Weights[i];
      BinValue += DataModel.Values[i];
    }
  }
  Console.WriteLine("Packed bin weight: " + BinWeight);
  Console.WriteLine("Packed bin value: " + BinValue);
  TotalWeight += BinWeight;
}
Console.WriteLine("Total packed weight: " + TotalWeight);

For each bin, the code displays the items placed that bin, as well as the bin's total value and weight. The code also displays the overall total value and weight of the packed items.

Output of the program

When you run the program, it displays the following output.

Total packed value: 395.0
Bin  0

Item 3 - weight: 36  value: 50
Item 13 - weight: 36  value: 30
Packed bin weight: 72
Packed bin value: 80

Bin  1

Item 5 - weight: 48  value: 30
Item 7 - weight: 42  value: 40
Packed bin weight: 90
Packed bin value: 70

Bin  2 

Item 1 - weight: 30  value: 30
Item 10 - weight: 30  value: 45
Item 14 - weight: 36  value: 25
Packed bin weight: 96
Packed bin value: 100

Bin  3

Item 2 - weight: 42  value: 25
Item 12 - weight: 42  value: 20
Packed bin weight: 84
Packed bin value: 45

Bin  4 

Item 4 - weight: 36  value: 35
Item 8 - weight: 36  value: 30
Item 9 - weight: 24  value: 35
Packed bin weight: 96
Packed bin value: 100

Total packed weight: 438

Complete programs

The complete programs for multiple knapsacks are shown below.

Python

from __future__ import print_function
from ortools.linear_solver import pywraplp



def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    values = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    data['weights'] = weights
    data['values'] = values
    data['items'] = list(range(len(weights)))
    data['num_items'] = len(weights)
    num_bins = 5
    data['bins'] = list(range(num_bins))
    data['bin_capacities'] = [100, 100, 100, 100, 100]
    return data




def main():
    data = create_data_model()

    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver('SCIP')

    # Variables
    # x[i, j] = 1 if item i is packed in bin j.
    x = {}
    for i in data['items']:
        for j in data['bins']:
            x[(i, j)] = solver.IntVar(0, 1, 'x_%i_%i' % (i, j))

    # Constraints
    # Each item can be in at most one bin.
    for i in data['items']:
        solver.Add(sum(x[i, j] for j in data['bins']) <= 1)
    # The amount packed in each bin cannot exceed its capacity.
    for j in data['bins']:
        solver.Add(
            sum(x[(i, j)] * data['weights'][i]
                for i in data['items']) <= data['bin_capacities'][j])

    # Objective
    objective = solver.Objective()

    for i in data['items']:
        for j in data['bins']:
            objective.SetCoefficient(x[(i, j)], data['values'][i])
    objective.SetMaximization()

    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print('Total packed value:', objective.Value())
        total_weight = 0
        for j in data['bins']:
            bin_weight = 0
            bin_value = 0
            print('Bin ', j, '\n')
            for i in data['items']:
                if x[i, j].solution_value() > 0:
                    print('Item', i, '- weight:', data['weights'][i], ' value:',
                          data['values'][i])
                    bin_weight += data['weights'][i]
                    bin_value += data['values'][i]
            print('Packed bin weight:', bin_weight)
            print('Packed bin value:', bin_value)
            print()
            total_weight += bin_weight
        print('Total packed weight:', total_weight)
    else:
        print('The problem does not have an optimal solution.')


if __name__ == '__main__':
    main()

C++

#include <iostream>
#include <numeric>
#include <vector>

#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
struct DataModel {
  const std::vector<int> weights = {48, 30, 42, 36, 36, 48, 42, 42,
                                    36, 24, 30, 30, 42, 36, 36};
  const std::vector<int> values = {10, 30, 25, 50, 35, 30, 15, 40,
                                   30, 35, 45, 10, 20, 30, 25};
  const int num_items = weights.size();
  const int total_value = std::accumulate(values.begin(), values.end(), 0);
  const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
  const int num_bins = 5;
};

void MultipleKnapsackMip() {
  DataModel data;

  // Create the mip solver with the CBC backend.
  MPSolver solver("multiple_knapsack_mip",
                  MPSolver::CBC_MIXED_INTEGER_PROGRAMMING);

  std::vector<std::vector<const MPVariable*>> x(
      data.num_items, std::vector<const MPVariable*>(data.num_bins));
  for (int i = 0; i < data.num_items; ++i) {
    for (int j = 0; j < data.num_bins; ++j) {
      x[i][j] = solver.MakeIntVar(0.0, 1.0, "");
    }
  }

  // Create the constraints.
  // Each item is in at most one bin.
  for (int i = 0; i < data.num_items; ++i) {
    LinearExpr sum;
    for (int j = 0; j < data.num_bins; ++j) {
      sum += x[i][j];
    }
    solver.MakeRowConstraint(sum <= 1.0);
  }
  // For each bin that is used, the total packed weight can be at most
  // the bin capacity.
  for (int j = 0; j < data.num_bins; ++j) {
    LinearExpr weight;
    for (int i = 0; i < data.num_items; ++i) {
      weight += data.weights[i] * LinearExpr(x[i][j]);
    }
    solver.MakeRowConstraint(weight <= data.bin_capacities[j]);
  }

  // Create the objective function.
  MPObjective* const objective = solver.MutableObjective();
  LinearExpr value;
  for (int i = 0; i < data.num_items; ++i) {
    for (int j = 0; j < data.num_bins; ++j) {
      value += data.values[i] * LinearExpr(x[i][j]);
    }
  }
  objective->MaximizeLinearExpr(value);

  const MPSolver::ResultStatus result_status = solver.Solve();

  // Check that the problem has an optimal solution.
  if (result_status != MPSolver::OPTIMAL) {
    std::cerr << "The problem does not have an optimal solution!";
  }
  std::cout << "Total packed value: " << objective->Value() << "\n\n";
  double total_weight = 0;
  for (int j = 0; j < data.num_bins; ++j) {
    double bin_weight = 0;
    double bin_value = 0;
    std::cout << "Bin " << j << std::endl << std::endl;
    for (int i = 0; i < data.num_items; ++i) {
      if (x[i][j]->solution_value() == 1) {
        std::cout << "Item " << i << " - weight: " << data.weights[i]
                  << "  value: " << data.values[i] << std::endl;
        bin_weight += data.weights[i];
        bin_value += data.values[i];
      }
    }
    std::cout << "Packed bin weight: " << bin_weight << std::endl;
    std::cout << "Packed bin value: " << bin_value << std::endl << std::endl;
    total_weight += bin_weight;
  }
  std::cout << "Total packed weight: " << total_weight << std::endl;
}
}  // namespace operations_research

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

Java

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Multiple knapsack problem. */
public class MultipleKnapsackMip {
  static class DataModel {
    public final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    public final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    public final int numItems = weights.length;
    public final int numBins = 5;
    public final double[] binCapacities = {100, 100, 100, 100, 100};
  }

  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    final DataModel data = new DataModel();

    // Create the linear solver with the SCIP backend.
    MPSolver solver = MPSolver.createSolver("SCIP");
    if (solver == null) {
      System.out.println("Could not create solver SCIP");
      return;
    }

    MPVariable[][] x = new MPVariable[data.numItems][data.numBins];
    for (int i = 0; i < data.numItems; ++i) {
      for (int j = 0; j < data.numBins; ++j) {
        x[i][j] = solver.makeIntVar(0, 1, "");
      }
    }

    for (int i = 0; i < data.numItems; ++i) {
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      for (int j = 0; j < data.numBins; ++j) {
        constraint.setCoefficient(x[i][j], 1);
      }
    }
    for (int j = 0; j < data.numBins; ++j) {
      MPConstraint constraint = solver.makeConstraint(0, data.binCapacities[j], "");
      for (int i = 0; i < data.numItems; ++i) {
        constraint.setCoefficient(x[i][j], data.weights[i]);
      }
    }

    MPObjective objective = solver.objective();
    for (int i = 0; i < data.numItems; ++i) {
      for (int j = 0; j < data.numBins; ++j) {
        objective.setCoefficient(x[i][j], data.values[i]);
      }
    }
    objective.setMaximization();

    final MPSolver.ResultStatus resultStatus = solver.solve();

    // Check that the problem has an optimal solution.
    if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
      System.out.println("Total packed value: " + objective.value() + "\n");
      double totalWeight = 0;
      for (int j = 0; j < data.numBins; ++j) {
        double binWeight = 0;
        double binValue = 0;
        System.out.println("Bin " + j + "\n");
        for (int i = 0; i < data.numItems; ++i) {
          if (x[i][j].solutionValue() == 1) {
            System.out.println(
                "Item " + i + " - weight: " + data.weights[i] + "  value: " + data.values[i]);
            binWeight += data.weights[i];
            binValue += data.values[i];
          }
        }
        System.out.println("Packed bin weight: " + binWeight);
        System.out.println("Packed bin value: " + binValue + "\n");
        totalWeight += binWeight;
      }
      System.out.println("Total packed weight: " + totalWeight);
    } else {
      System.err.println("The problem does not have an optimal solution.");
    }
  }

  private MultipleKnapsackMip() {}
}

C#

using System;
using Google.OrTools.LinearSolver;

public class MultipleKnapsackMip
{
  class DataModel
  {
    public static double[] Weights =
      {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    public static double[] Values =
      {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    public double[] BinCapacities = {100, 100, 100, 100, 100};
    public int NumItems = Weights.Length;
    public int NumBins = 5;
  }
  public static void Main()
  {
    DataModel data = new DataModel();

    // Create the linear solver with the SCIP backend.
    Solver solver = Solver.CreateSolver("SCIP");

    Variable[,] x = new Variable[data.NumItems, data.NumBins];
    for (int i = 0; i < data.NumItems; i++)
    {
      for (int j = 0; j < data.NumBins; j++)
      {
        x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
      }
    }

    for (int i = 0; i < data.NumItems; ++i) {
      Constraint constraint = solver.MakeConstraint(0, 1, "");
      for (int j = 0; j < data.NumBins; ++j) {
        constraint.SetCoefficient(x[i, j], 1);
      }
    }

    for (int j = 0; j < data.NumBins; ++j)
    {
      Constraint constraint = solver.MakeConstraint(0, data.BinCapacities[j], "");
      for (int i = 0; i < data.NumItems; ++i)
      {
        constraint.SetCoefficient(x[i, j], DataModel.Weights[i]);
      }
    }

    Objective objective = solver.Objective();
    for (int i = 0; i < data.NumItems; ++i)
    {
      for (int j = 0; j < data.NumBins; ++j)
      {
        objective.SetCoefficient(x[i, j], DataModel.Values[i]);
      }
    }
    objective.SetMaximization();

    Solver.ResultStatus resultStatus = solver.Solve();

    // Check that the problem has an optimal solution.
    if (resultStatus != Solver.ResultStatus.OPTIMAL)
    {
      Console.WriteLine("The problem does not have an optimal solution!");
      return;
    }
    Console.WriteLine("Total packed value: " + solver.Objective().Value());
    double TotalWeight = 0.0;
    for (int j = 0; j < data.NumBins; ++j)
    {
      double BinWeight = 0.0;
      double BinValue = 0.0;
      Console.WriteLine("Bin " + j);
      for (int i = 0; i < data.NumItems; ++i)
      {
        if (x[i, j].SolutionValue() == 1)
        {
          Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]} values: {DataModel.Values[i]}");
          BinWeight += DataModel.Weights[i];
          BinValue += DataModel.Values[i];
        }
      }
      Console.WriteLine("Packed bin weight: " + BinWeight);
      Console.WriteLine("Packed bin value: " + BinValue);
      TotalWeight += BinWeight;
    }
    Console.WriteLine("Total packed weight: " + TotalWeight);
  }
}