本頁面由 Cloud Translation API 翻譯而成。

特徵包裝問題

和多個 knackack 問題一樣，bin packing 問題也涉及將項目封裝至 bin。但是，二進位封裝問題有不同的目標：找出包含所有項目的最小 bin。

以下摘要說明這兩種問題的差異：

多個 knaackack 問題：將一部分項目封裝到固定數量的 bin 中，容量不同，因此封裝項目的總值最大值。
特徵分塊封裝問題：由於需要多少具備共同容量的特徵分塊，請找出包含所有項目的最小特徵分塊。在本問題中，這些項目並未指派值，因為目標不包含值。

下一個範例說明如何解決 bin 裝箱問題。

範例

在這個範例中，不同重量的項目必須封裝成一組具有共同容量的特徵分塊。假設有足夠的 bin 能夠存放所有項目，問題就是要找出充足的最少。

下列各節提供了能解決這個問題的計劃。如需完整的程式，請參閱完成程式一文。

這個範例使用 MPSolver 包裝函式。

匯入程式庫

下列程式碼會匯入必要的程式庫。

Python

from ortools.linear_solver import pywraplp

C++

#include <iostream>
#include <memory>
#include <numeric>
#include <ostream>
#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;

建立資料

以下程式碼會建立範例的資料。

Python

def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
    data["weights"] = weights
    data["items"] = list(range(len(weights)))
    data["bins"] = data["items"]
    data["bin_capacity"] = 100
    return data

C++

struct DataModel {
  const std::vector<double> weights = {48, 30, 19, 36, 36, 27,
                                       42, 42, 36, 24, 30};
  const int num_items = weights.size();
  const int num_bins = weights.size();
  const int bin_capacity = 100;
};

Java

static class DataModel {
  public final double[] weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
  public final int numItems = weights.length;
  public final int numBins = weights.length;
  public final int binCapacity = 100;
}

C#

class DataModel
{
    public static double[] Weights = { 48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30 };
    public int NumItems = Weights.Length;
    public int NumBins = Weights.Length;
    public double BinCapacity = 100.0;
}

包括：

weights：包含項目權重的向量。
bin_capacity：提供二元容量的數值。

系統不會為項目指派任何值，因為最小化 bin 數量的目標不會涉及值。

請注意，num_bins 已設為項目數量。這是因為如果問題的解決方法是，則每個項目的權重必須小於或等於 bin 容量。在這種情況下，您需要的 bin 數量上限就是項目數量，因為您隨時可以將每個項目放入一個獨立的 bin。

宣告解題工具

以下程式碼宣告解題工具。

Python

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

  if not solver:
      return

C++

  // Create the mip solver with the SCIP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

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");
      if (solver is null)
      {
          return;
      }

建立變數

下列程式碼會建立程式的變數。

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

# y[j] = 1 if bin j is used.
y = {}
for j in data["bins"]:
    y[j] = solver.IntVar(0, 1, "y[%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, "");
  }
}
// y[j] = 1 if bin j is used.
std::vector<const MPVariable*> y(data.num_bins);
for (int j = 0; j < data.num_bins; ++j) {
  y[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, "");
  }
}
MPVariable[] y = new MPVariable[data.numBins];
for (int j = 0; j < data.numBins; ++j) {
  y[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}");
    }
}
Variable[] y = new Variable[data.NumBins];
for (int j = 0; j < data.NumBins; j++)
{
    y[j] = solver.MakeIntVar(0, 1, $"y_{j}");
}

和多個 knapack 範例一樣，您可以定義變數陣列 x[(i, j)]，如果將 i 放置在 bin j 中，其值為 1，否則為 0。

針對 bin 封裝，您也需定義變數 y[j] 的值，如果使用 bin j，其值為 1 (如果其中已納入任何項目)，則變數為 1，否則為 0。y[j] 的總和就是使用的二進位數。

定義限制條件

以下程式碼會定義問題的限制：

Python

# Constraints
# Each item must be in exactly 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"])
        <= y[j] * data["bin_capacity"]
    )

C++

// Create the constraints.
// Each item is in exactly 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 <= LinearExpr(y[j]) * data.bin_capacity);
}

Java

double infinity = java.lang.Double.POSITIVE_INFINITY;
for (int i = 0; i < data.numItems; ++i) {
  MPConstraint constraint = solver.makeConstraint(1, 1, "");
  for (int j = 0; j < data.numBins; ++j) {
    constraint.setCoefficient(x[i][j], 1);
  }
}
// The bin capacity contraint for bin j is
//   sum_i w_i x_ij <= C*y_j
// To define this constraint, first subtract the left side from the right to get
//   0 <= C*y_j - sum_i w_i x_ij
//
// Note: Since sum_i w_i x_ij is positive (and y_j is 0 or 1), the right side must
// be less than or equal to C. But it's not necessary to add this constraint
// because it is forced by the other constraints.

for (int j = 0; j < data.numBins; ++j) {
  MPConstraint constraint = solver.makeConstraint(0, infinity, "");
  constraint.setCoefficient(y[j], data.binCapacity);
  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(1, 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, Double.PositiveInfinity, "");
    constraint.SetCoefficient(y[j], data.BinCapacity);
    for (int i = 0; i < data.NumItems; ++i)
    {
        constraint.SetCoefficient(x[i, j], -DataModel.Weights[i]);
    }
}

限制如下：

每個項目都必須放在一個二進位區中。這項限制需要設定所有二進位 j 的 x[i][j] 總和等於 1，才能設定這項限制。請注意，這與多種 knaackack 問題不同，後者只需要總和小於或等於 1，因為並非所有項目都可以封裝。
每個箱裝箱總重量不得超過其容量。這與多個 knaackack 問題中的限制相同，但在這種情況下，您可以將不等式右側的二進位容量乘以 y[j]。

為什麼要乘以 y[j]？因為如果任何項目都包在二進位檔案 j 中，就會強制 y[j] 等於 1。因此，如果 y[j] 為 0，則不等式的右邊將為 0，而左側的 bin 權重將大於 0，這違反了限制。這會將變數 y[j] 與問題的目標連結，目前解析器會嘗試將 y[j] 為 1 的二進位數最小化。

設定目標

以下程式碼會定義問題的目標函式。

Python

# Objective: minimize the number of bins used.
solver.Minimize(solver.Sum([y[j] for j in data["bins"]]))

C++

// Create the objective function.
MPObjective* const objective = solver->MutableObjective();
LinearExpr num_bins_used;
for (int j = 0; j < data.num_bins; ++j) {
  num_bins_used += y[j];
}
objective->MinimizeLinearExpr(num_bins_used);

Java

MPObjective objective = solver.objective();
for (int j = 0; j < data.numBins; ++j) {
  objective.setCoefficient(y[j], 1);
}
objective.setMinimization();

C#

Objective objective = solver.Objective();
for (int j = 0; j < data.NumBins; ++j)
{
    objective.SetCoefficient(y[j], 1);
}
objective.SetMinimization();

由於使用 j 時，y[j] 為 1，否則為 0，則 y[j] 的總和就是使用的 bin 數量。其目標是盡可能減少總和。

呼叫解題工具並列印解決方案

下列程式碼會呼叫解題工具並列印解決方案。

Python

print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    num_bins = 0
    for j in data["bins"]:
        if y[j].solution_value() == 1:
            bin_items = []
            bin_weight = 0
            for i in data["items"]:
                if x[i, j].solution_value() > 0:
                    bin_items.append(i)
                    bin_weight += data["weights"][i]
            if bin_items:
                num_bins += 1
                print("Bin number", j)
                print("  Items packed:", bin_items)
                print("  Total weight:", bin_weight)
                print()
    print()
    print("Number of bins used:", num_bins)
    print("Time = ", solver.WallTime(), " milliseconds")
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!";
  return;
}
std::cout << "Number of bins used: " << objective->Value() << std::endl
          << std::endl;
double total_weight = 0;
for (int j = 0; j < data.num_bins; ++j) {
  if (y[j]->solution_value() == 1) {
    std::cout << "Bin " << j << std::endl << std::endl;
    double bin_weight = 0;
    for (int i = 0; i < data.num_items; ++i) {
      if (x[i][j]->solution_value() == 1) {
        std::cout << "Item " << i << " - Weight: " << data.weights[i]
                  << std::endl;
        bin_weight += data.weights[i];
      }
    }
    std::cout << "Packed bin weight: " << bin_weight << 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("Number of bins used: " + objective.value());
  double totalWeight = 0;
  for (int j = 0; j < data.numBins; ++j) {
    if (y[j].solutionValue() == 1) {
      System.out.println("\nBin " + j + "\n");
      double binWeight = 0;
      for (int i = 0; i < data.numItems; ++i) {
        if (x[i][j].solutionValue() == 1) {
          System.out.println("Item " + i + " - weight: " + data.weights[i]);
          binWeight += data.weights[i];
        }
      }
      System.out.println("Packed bin weight: " + binWeight);
      totalWeight += binWeight;
    }
  }
  System.out.println("\nTotal 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($"Number of bins used: {solver.Objective().Value()}");
double TotalWeight = 0.0;
for (int j = 0; j < data.NumBins; ++j)
{
    double BinWeight = 0.0;
    if (y[j].SolutionValue() == 1)
    {
        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]}");
                BinWeight += DataModel.Weights[i];
            }
        }
        Console.WriteLine($"Packed bin weight: {BinWeight}");
        TotalWeight += BinWeight;
    }
}
Console.WriteLine($"Total packed weight: {TotalWeight}");

這項解決方案會顯示打包所有項目所需的最低二進位數。針對使用中的每一個 bin，解決方案會顯示包裝中的項目，以及 bin 的總權重。

程式的輸出結果

當您執行該程式時，會顯示下列輸出結果。

Bin number 0
  Items packed: [1, 5, 10]
  Total weight: 87

Bin number 1
  Items packed: [0, 6]
  Total weight: 90

Bin number 2
  Items packed: [2, 4, 7]
  Total weight: 97

Bin number 3
  Items packed: [3, 8, 9]
  Total weight: 96


Number of bins used: 4.0

完成計畫

以下為 bin 裝箱問題的完整程式。

Python

from ortools.linear_solver import pywraplp


def create_data_model():
    """Create the data for the example."""
    data = {}
    weights = [48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30]
    data["weights"] = weights
    data["items"] = list(range(len(weights)))
    data["bins"] = data["items"]
    data["bin_capacity"] = 100
    return data



def main():
    data = create_data_model()

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

    if not solver:
        return

    # 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))

    # y[j] = 1 if bin j is used.
    y = {}
    for j in data["bins"]:
        y[j] = solver.IntVar(0, 1, "y[%i]" % j)

    # Constraints
    # Each item must be in exactly 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"])
            <= y[j] * data["bin_capacity"]
        )

    # Objective: minimize the number of bins used.
    solver.Minimize(solver.Sum([y[j] for j in data["bins"]]))

    print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        num_bins = 0
        for j in data["bins"]:
            if y[j].solution_value() == 1:
                bin_items = []
                bin_weight = 0
                for i in data["items"]:
                    if x[i, j].solution_value() > 0:
                        bin_items.append(i)
                        bin_weight += data["weights"][i]
                if bin_items:
                    num_bins += 1
                    print("Bin number", j)
                    print("  Items packed:", bin_items)
                    print("  Total weight:", bin_weight)
                    print()
        print()
        print("Number of bins used:", num_bins)
        print("Time = ", solver.WallTime(), " milliseconds")
    else:
        print("The problem does not have an optimal solution.")


if __name__ == "__main__":
    main()

C++

#include <iostream>
#include <memory>
#include <numeric>
#include <ostream>
#include <vector>

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

namespace operations_research {
struct DataModel {
  const std::vector<double> weights = {48, 30, 19, 36, 36, 27,
                                       42, 42, 36, 24, 30};
  const int num_items = weights.size();
  const int num_bins = weights.size();
  const int bin_capacity = 100;
};

void BinPackingMip() {
  DataModel data;

  // Create the mip solver with the SCIP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
  if (!solver) {
    LOG(WARNING) << "SCIP solver unavailable.";
    return;
  }

  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, "");
    }
  }
  // y[j] = 1 if bin j is used.
  std::vector<const MPVariable*> y(data.num_bins);
  for (int j = 0; j < data.num_bins; ++j) {
    y[j] = solver->MakeIntVar(0.0, 1.0, "");
  }

  // Create the constraints.
  // Each item is in exactly 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 <= LinearExpr(y[j]) * data.bin_capacity);
  }

  // Create the objective function.
  MPObjective* const objective = solver->MutableObjective();
  LinearExpr num_bins_used;
  for (int j = 0; j < data.num_bins; ++j) {
    num_bins_used += y[j];
  }
  objective->MinimizeLinearExpr(num_bins_used);

  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!";
    return;
  }
  std::cout << "Number of bins used: " << objective->Value() << std::endl
            << std::endl;
  double total_weight = 0;
  for (int j = 0; j < data.num_bins; ++j) {
    if (y[j]->solution_value() == 1) {
      std::cout << "Bin " << j << std::endl << std::endl;
      double bin_weight = 0;
      for (int i = 0; i < data.num_items; ++i) {
        if (x[i][j]->solution_value() == 1) {
          std::cout << "Item " << i << " - Weight: " << data.weights[i]
                    << std::endl;
          bin_weight += data.weights[i];
        }
      }
      std::cout << "Packed bin weight: " << bin_weight << 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::BinPackingMip();
  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;

/** Bin packing problem. */
public class BinPackingMip {
  static class DataModel {
    public final double[] weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
    public final int numItems = weights.length;
    public final int numBins = weights.length;
    public final int binCapacity = 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, "");
      }
    }
    MPVariable[] y = new MPVariable[data.numBins];
    for (int j = 0; j < data.numBins; ++j) {
      y[j] = solver.makeIntVar(0, 1, "");
    }

    double infinity = java.lang.Double.POSITIVE_INFINITY;
    for (int i = 0; i < data.numItems; ++i) {
      MPConstraint constraint = solver.makeConstraint(1, 1, "");
      for (int j = 0; j < data.numBins; ++j) {
        constraint.setCoefficient(x[i][j], 1);
      }
    }
    // The bin capacity contraint for bin j is
    //   sum_i w_i x_ij <= C*y_j
    // To define this constraint, first subtract the left side from the right to get
    //   0 <= C*y_j - sum_i w_i x_ij
    //
    // Note: Since sum_i w_i x_ij is positive (and y_j is 0 or 1), the right side must
    // be less than or equal to C. But it's not necessary to add this constraint
    // because it is forced by the other constraints.

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

    MPObjective objective = solver.objective();
    for (int j = 0; j < data.numBins; ++j) {
      objective.setCoefficient(y[j], 1);
    }
    objective.setMinimization();

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

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

C#

using System;
using Google.OrTools.LinearSolver;

public class BinPackingMip
{
    class DataModel
    {
        public static double[] Weights = { 48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30 };
        public int NumItems = Weights.Length;
        public int NumBins = Weights.Length;
        public double BinCapacity = 100.0;
    }
    public static void Main()
    {
        DataModel data = new DataModel();

        // Create the linear solver with the SCIP backend.
        Solver solver = Solver.CreateSolver("SCIP");
        if (solver is null)
        {
            return;
        }

        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}");
            }
        }
        Variable[] y = new Variable[data.NumBins];
        for (int j = 0; j < data.NumBins; j++)
        {
            y[j] = solver.MakeIntVar(0, 1, $"y_{j}");
        }

        for (int i = 0; i < data.NumItems; ++i)
        {
            Constraint constraint = solver.MakeConstraint(1, 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, Double.PositiveInfinity, "");
            constraint.SetCoefficient(y[j], data.BinCapacity);
            for (int i = 0; i < data.NumItems; ++i)
            {
                constraint.SetCoefficient(x[i, j], -DataModel.Weights[i]);
            }
        }

        Objective objective = solver.Objective();
        for (int j = 0; j < data.NumBins; ++j)
        {
            objective.SetCoefficient(y[j], 1);
        }
        objective.SetMinimization();

        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($"Number of bins used: {solver.Objective().Value()}");
        double TotalWeight = 0.0;
        for (int j = 0; j < data.NumBins; ++j)
        {
            double BinWeight = 0.0;
            if (y[j].SolutionValue() == 1)
            {
                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]}");
                        BinWeight += DataModel.Weights[i];
                    }
                }
                Console.WriteLine($"Packed bin weight: {BinWeight}");
                TotalWeight += BinWeight;
            }
        }
        Console.WriteLine($"Total packed weight: {TotalWeight}");
    }
}