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

解決多個 Knapsacks 問題

本節說明如何解決多個 Knaps 的 Knapsack 問題使用 MIP 解析器和 CP-SAT 解析器。在此情況下，容器通常會稱為「bins」，而非 K 線。

下一個範例顯示如何找出將商品包裝成五個特徵分塊的最佳方式。

範例

如先前的範例所示，您需從不同權重和值的項目集合。問題是每個特徵分塊的特徵分塊，每個特徵分塊的容量上限為 100 ，確保封裝值是最大值。

以下各節說明能解決這個問題的程式章節。如要參加完整計畫，請參閱「完成計畫」。

MIP 解決方案

以下各節說明如何使用 MPSolver 包裝函式。

匯入程式庫

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

Python

from ortools.linear_solver import pywraplp

C++

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

#include "absl/strings/str_format.h"
#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;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

建立資料

下列程式碼會建立問題資料。

Python

data = {}
data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
assert len(data["weights"]) == len(data["values"])
data["num_items"] = len(data["weights"])
data["all_items"] = range(data["num_items"])

data["bin_capacities"] = [100, 100, 100, 100, 100]
data["num_bins"] = len(data["bin_capacities"])
data["all_bins"] = range(data["num_bins"])

C++

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();
std::vector<int> all_items(num_items);
std::iota(all_items.begin(), all_items.end(), 0);

const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
const int num_bins = bin_capacities.size();
std::vector<int> all_bins(num_bins);
std::iota(all_bins.begin(), all_bins.end(), 0);

Java

final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
final int numItems = weights.length;
final int[] allItems = IntStream.range(0, numItems).toArray();

final double[] binCapacities = {100, 100, 100, 100, 100};
final int numBins = binCapacities.length;
final int[] allBins = IntStream.range(0, numBins).toArray();

C#

double[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
double[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();

double[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();

相關資料包括：

weights：包含項目權重的向量。
values：包含項目值的向量。
capacities：包含特徵分塊容量的向量。

在這個範例中，所有特徵分塊的容量都相同，但不需要如此

宣告 MIP 解析器

下列程式碼宣告 MIP 解析器。

Python

solver = pywraplp.Solver.CreateSolver("SCIP")
if solver is None:
    print("SCIP solver unavailable.")
    return

C++

  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

# x[i, b] = 1 if item i is packed in bin b.
x = {}
for i in data["all_items"]:
    for b in data["all_bins"]:
        x[i, b] = solver.BoolVar(f"x_{i}_{b}")

C++

// x[i][b] = 1 if item i is packed in bin b.
std::vector<std::vector<const MPVariable*>> x(
    num_items, std::vector<const MPVariable*>(num_bins));
for (int i : all_items) {
  for (int b : all_bins) {
    x[i][b] = solver->MakeBoolVar(absl::StrFormat("x_%d_%d", i, b));
  }
}

Java

MPVariable[][] x = new MPVariable[numItems][numBins];
for (int i : allItems) {
  for (int b : allBins) {
    x[i][b] = solver.makeBoolVar("x_" + i + "_" + b);
  }
}

C#

Variable[,] x = new Variable[NumItems, NumBins];
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        x[i, b] = solver.MakeBoolVar($"x_{i}_{b}");
    }
}

每個 x[(i, j)] 都是 0-1 變數，其中 i 是項目，j 是特徵分塊。於解決方案；如果將項目 i 放在特徵分塊 j 中，x[(i, j)] 將會是 1，而 0 反之。

定義限制

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

Python

# Each item is assigned to at most one bin.
for i in data["all_items"]:
    solver.Add(sum(x[i, b] for b in data["all_bins"]) <= 1)

# The amount packed in each bin cannot exceed its capacity.
for b in data["all_bins"]:
    solver.Add(
        sum(x[i, b] * data["weights"][i] for i in data["all_items"])
        <= data["bin_capacities"][b]
    )

C++

// Each item is assigned to at most one bin.
for (int i : all_items) {
  LinearExpr sum;
  for (int b : all_bins) {
    sum += x[i][b];
  }
  solver->MakeRowConstraint(sum <= 1.0);
}
// The amount packed in each bin cannot exceed its capacity.
for (int b : all_bins) {
  LinearExpr bin_weight;
  for (int i : all_items) {
    bin_weight += LinearExpr(x[i][b]) * weights[i];
  }
  solver->MakeRowConstraint(bin_weight <= bin_capacities[b]);
}

Java

// Each item is assigned to at most one bin.
for (int i : allItems) {
  MPConstraint constraint = solver.makeConstraint(0, 1, "");
  for (int b : allBins) {
    constraint.setCoefficient(x[i][b], 1);
  }
}

// The amount packed in each bin cannot exceed its capacity.
for (int b : allBins) {
  MPConstraint constraint = solver.makeConstraint(0, binCapacities[b], "");
  for (int i : allItems) {
    constraint.setCoefficient(x[i][b], weights[i]);
  }
}

C#

// Each item is assigned to at most one bin.
foreach (int i in allItems)
{
    Constraint constraint = solver.MakeConstraint(0, 1, "");
    foreach (int b in allBins)
    {
        constraint.SetCoefficient(x[i, b], 1);
    }
}

// The amount packed in each bin cannot exceed its capacity.
foreach (int b in allBins)
{
    Constraint constraint = solver.MakeConstraint(0, BinCapacities[b], "");
    foreach (int i in allItems)
    {
        constraint.SetCoefficient(x[i, b], Weights[i]);
    }
}

限制如下：

每個項目最多只能放在一個特徵分塊中。這項限制是由要求 j 所有特徵分塊的 x[i, j] 總和必須小於或等於 1。
每個特徵分塊中包裝的總重量不得超過其容量。這個設定限制條件的方式，是要求特徵分塊中放置項目的權重總和 j 必須小於或等於特徵分塊的容量。

定義目標

下列程式碼定義問題的目標函式，也就是計算包裝項目的總價值。

Python

# Maximize total value of packed items.
objective = solver.Objective()
for i in data["all_items"]:
    for b in data["all_bins"]:
        objective.SetCoefficient(x[i, b], data["values"][i])
objective.SetMaximization()

C++

// Maximize total value of packed items.
MPObjective* const objective = solver->MutableObjective();
LinearExpr objective_value;
for (int i : all_items) {
  for (int b : all_bins) {
    objective_value += LinearExpr(x[i][b]) * values[i];
  }
}
objective->MaximizeLinearExpr(objective_value);

Java

// Maximize total value of packed items.
MPObjective objective = solver.objective();
for (int i : allItems) {
  for (int b : allBins) {
    objective.setCoefficient(x[i][b], values[i]);
  }
}
objective.setMaximization();

C#

Objective objective = solver.Objective();
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        objective.SetCoefficient(x[i, b], Values[i]);
    }
}
objective.SetMaximization();

請注意，x[i, j] * data['values'][i] 會將項目 i 的值加入並將目標放在 bin j 中。如果 i 未放入任何特徵分塊，也不會對目標做出貢獻

叫用解題工具

下列程式碼會叫用解題工具。

Python

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

C++

const MPSolver::ResultStatus result_status = solver->Solve();

Java

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

C#

Solver.ResultStatus resultStatus = solver.Solve();

列印解決方案

下列程式碼會顯示問題的解決方案。

Python

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

C++

if (result_status == MPSolver::OPTIMAL) {
  LOG(INFO) << "Total packed value: " << objective->Value();
  double total_weight = 0.0;
  for (int b : all_bins) {
    LOG(INFO) << "Bin " << b;
    double bin_weight = 0.0;
    double bin_value = 0.0;
    for (int i : all_items) {
      if (x[i][b]->solution_value() > 0) {
        LOG(INFO) << "Item " << i << " weight: " << weights[i]
                  << " value: " << values[i];
        bin_weight += weights[i];
        bin_value += values[i];
      }
    }
    LOG(INFO) << "Packed bin weight: " << bin_weight;
    LOG(INFO) << "Packed bin value: " << bin_value;
    total_weight += bin_weight;
  }
  LOG(INFO) << "Total packed weight: " << total_weight;
} else {
  LOG(INFO) << "The problem does not have an optimal solution.";
}

Java

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

C#

// Check that the problem has an optimal solution.
if (resultStatus == Solver.ResultStatus.OPTIMAL)
{
    Console.WriteLine($"Total packed value: {solver.Objective().Value()}");
    double TotalWeight = 0.0;
    foreach (int b in allBins)
    {
        double BinWeight = 0.0;
        double BinValue = 0.0;
        Console.WriteLine("Bin " + b);
        foreach (int i in allItems)
        {
            if (x[i, b].SolutionValue() == 1)
            {
                Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                BinWeight += Weights[i];
                BinValue += Values[i];
            }
        }
        Console.WriteLine("Packed bin weight: " + BinWeight);
        Console.WriteLine("Packed bin value: " + BinValue);
        TotalWeight += BinWeight;
    }
    Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
    Console.WriteLine("The problem does not have an optimal solution!");
}

程式碼會顯示每個特徵分塊放置的項目，以及特徵分塊總值和權重程式碼也會顯示整體總價值計算包裝物品的重量。

執行程式時，系統會顯示下列輸出內容。

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

完成計畫

以下是多個刀具適用的完整計畫。

Python

"""Solve a multiple knapsack problem using a MIP solver."""
from ortools.linear_solver import pywraplp


def main():
    data = {}
    data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    assert len(data["weights"]) == len(data["values"])
    data["num_items"] = len(data["weights"])
    data["all_items"] = range(data["num_items"])

    data["bin_capacities"] = [100, 100, 100, 100, 100]
    data["num_bins"] = len(data["bin_capacities"])
    data["all_bins"] = range(data["num_bins"])

    # Create the mip solver with the SCIP backend.
    solver = pywraplp.Solver.CreateSolver("SCIP")
    if solver is None:
        print("SCIP solver unavailable.")
        return

    # Variables.
    # x[i, b] = 1 if item i is packed in bin b.
    x = {}
    for i in data["all_items"]:
        for b in data["all_bins"]:
            x[i, b] = solver.BoolVar(f"x_{i}_{b}")

    # Constraints.
    # Each item is assigned to at most one bin.
    for i in data["all_items"]:
        solver.Add(sum(x[i, b] for b in data["all_bins"]) <= 1)

    # The amount packed in each bin cannot exceed its capacity.
    for b in data["all_bins"]:
        solver.Add(
            sum(x[i, b] * data["weights"][i] for i in data["all_items"])
            <= data["bin_capacities"][b]
        )

    # Objective.
    # Maximize total value of packed items.
    objective = solver.Objective()
    for i in data["all_items"]:
        for b in data["all_bins"]:
            objective.SetCoefficient(x[i, b], data["values"][i])
    objective.SetMaximization()

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

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


if __name__ == "__main__":
    main()

C++

// Solve a multiple knapsack problem using a MIP solver.
#include <iostream>
#include <memory>
#include <numeric>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {

void MultipleKnapsackMip() {
  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();
  std::vector<int> all_items(num_items);
  std::iota(all_items.begin(), all_items.end(), 0);

  const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
  const int num_bins = bin_capacities.size();
  std::vector<int> all_bins(num_bins);
  std::iota(all_bins.begin(), all_bins.end(), 0);

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

  // Variables.
  // x[i][b] = 1 if item i is packed in bin b.
  std::vector<std::vector<const MPVariable*>> x(
      num_items, std::vector<const MPVariable*>(num_bins));
  for (int i : all_items) {
    for (int b : all_bins) {
      x[i][b] = solver->MakeBoolVar(absl::StrFormat("x_%d_%d", i, b));
    }
  }

  // Constraints.
  // Each item is assigned to at most one bin.
  for (int i : all_items) {
    LinearExpr sum;
    for (int b : all_bins) {
      sum += x[i][b];
    }
    solver->MakeRowConstraint(sum <= 1.0);
  }
  // The amount packed in each bin cannot exceed its capacity.
  for (int b : all_bins) {
    LinearExpr bin_weight;
    for (int i : all_items) {
      bin_weight += LinearExpr(x[i][b]) * weights[i];
    }
    solver->MakeRowConstraint(bin_weight <= bin_capacities[b]);
  }

  // Objective.
  // Maximize total value of packed items.
  MPObjective* const objective = solver->MutableObjective();
  LinearExpr objective_value;
  for (int i : all_items) {
    for (int b : all_bins) {
      objective_value += LinearExpr(x[i][b]) * values[i];
    }
  }
  objective->MaximizeLinearExpr(objective_value);

  const MPSolver::ResultStatus result_status = solver->Solve();

  if (result_status == MPSolver::OPTIMAL) {
    LOG(INFO) << "Total packed value: " << objective->Value();
    double total_weight = 0.0;
    for (int b : all_bins) {
      LOG(INFO) << "Bin " << b;
      double bin_weight = 0.0;
      double bin_value = 0.0;
      for (int i : all_items) {
        if (x[i][b]->solution_value() > 0) {
          LOG(INFO) << "Item " << i << " weight: " << weights[i]
                    << " value: " << values[i];
          bin_weight += weights[i];
          bin_value += values[i];
        }
      }
      LOG(INFO) << "Packed bin weight: " << bin_weight;
      LOG(INFO) << "Packed bin value: " << bin_value;
      total_weight += bin_weight;
    }
    LOG(INFO) << "Total packed weight: " << total_weight;
  } else {
    LOG(INFO) << "The problem does not have an optimal solution.";
  }
}
}  // namespace operations_research

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

Java

// Solve a multiple knapsack problem using a MIP solver.
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;
import java.util.stream.IntStream;

/** Multiple knapsack problem. */
public class MultipleKnapsackMip {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Instantiate the data problem.
    final double[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    final double[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    final int numItems = weights.length;
    final int[] allItems = IntStream.range(0, numItems).toArray();

    final double[] binCapacities = {100, 100, 100, 100, 100};
    final int numBins = binCapacities.length;
    final int[] allBins = IntStream.range(0, numBins).toArray();

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

    // Variables.
    MPVariable[][] x = new MPVariable[numItems][numBins];
    for (int i : allItems) {
      for (int b : allBins) {
        x[i][b] = solver.makeBoolVar("x_" + i + "_" + b);
      }
    }

    // Constraints.
    // Each item is assigned to at most one bin.
    for (int i : allItems) {
      MPConstraint constraint = solver.makeConstraint(0, 1, "");
      for (int b : allBins) {
        constraint.setCoefficient(x[i][b], 1);
      }
    }

    // The amount packed in each bin cannot exceed its capacity.
    for (int b : allBins) {
      MPConstraint constraint = solver.makeConstraint(0, binCapacities[b], "");
      for (int i : allItems) {
        constraint.setCoefficient(x[i][b], weights[i]);
      }
    }

    // Objective.
    // Maximize total value of packed items.
    MPObjective objective = solver.objective();
    for (int i : allItems) {
      for (int b : allBins) {
        objective.setCoefficient(x[i][b], values[i]);
      }
    }
    objective.setMaximization();

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

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

  private MultipleKnapsackMip() {}
}

C#

// Solve a multiple knapsack problem using a MIP solver.
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;

public class MultipleKnapsackMip
{
    public static void Main()
    {
        // Instantiate the data problem.
        double[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
        double[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
        int NumItems = Weights.Length;
        int[] allItems = Enumerable.Range(0, NumItems).ToArray();

        double[] BinCapacities = { 100, 100, 100, 100, 100 };
        int NumBins = BinCapacities.Length;
        int[] allBins = Enumerable.Range(0, NumBins).ToArray();

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

        // Variables.
        Variable[,] x = new Variable[NumItems, NumBins];
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                x[i, b] = solver.MakeBoolVar($"x_{i}_{b}");
            }
        }

        // Constraints.
        // Each item is assigned to at most one bin.
        foreach (int i in allItems)
        {
            Constraint constraint = solver.MakeConstraint(0, 1, "");
            foreach (int b in allBins)
            {
                constraint.SetCoefficient(x[i, b], 1);
            }
        }

        // The amount packed in each bin cannot exceed its capacity.
        foreach (int b in allBins)
        {
            Constraint constraint = solver.MakeConstraint(0, BinCapacities[b], "");
            foreach (int i in allItems)
            {
                constraint.SetCoefficient(x[i, b], Weights[i]);
            }
        }

        // Objective.
        Objective objective = solver.Objective();
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                objective.SetCoefficient(x[i, b], Values[i]);
            }
        }
        objective.SetMaximization();

        Solver.ResultStatus resultStatus = solver.Solve();

        // Check that the problem has an optimal solution.
        if (resultStatus == Solver.ResultStatus.OPTIMAL)
        {
            Console.WriteLine($"Total packed value: {solver.Objective().Value()}");
            double TotalWeight = 0.0;
            foreach (int b in allBins)
            {
                double BinWeight = 0.0;
                double BinValue = 0.0;
                Console.WriteLine("Bin " + b);
                foreach (int i in allItems)
                {
                    if (x[i, b].SolutionValue() == 1)
                    {
                        Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                        BinWeight += Weights[i];
                        BinValue += Values[i];
                    }
                }
                Console.WriteLine("Packed bin weight: " + BinWeight);
                Console.WriteLine("Packed bin value: " + BinValue);
                TotalWeight += BinWeight;
            }
            Console.WriteLine("Total packed weight: " + TotalWeight);
        }
        else
        {
            Console.WriteLine("The problem does not have an optimal solution!");
        }
    }
}

CP SAT 解決方案

以下各節說明如何使用 CP-SAT 解析器解決問題。

匯入程式庫

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

Python

from ortools.sat.python import cp_model

C++

#include <stdlib.h>

#include <map>
#include <numeric>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

C#

using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class MultipleKnapsackSat
{
    public static void Main(String[] args)
    {
        // Instantiate the data problem.
        int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
        int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
        int NumItems = Weights.Length;
        int[] allItems = Enumerable.Range(0, NumItems).ToArray();

        int[] BinCapacities = { 100, 100, 100, 100, 100 };
        int NumBins = BinCapacities.Length;
        int[] allBins = Enumerable.Range(0, NumBins).ToArray();

        // Model.
        CpModel model = new CpModel();

        // Variables.
        ILiteral[,] x = new ILiteral[NumItems, NumBins];
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                x[i, b] = model.NewBoolVar($"x_{i}_{b}");
            }
        }

        // Constraints.
        // Each item is assigned to at most one bin.
        foreach (int i in allItems)
        {
            List<ILiteral> literals = new List<ILiteral>();
            foreach (int b in allBins)
            {
                literals.Add(x[i, b]);
            }
            model.AddAtMostOne(literals);
        }

        // The amount packed in each bin cannot exceed its capacity.
        foreach (int b in allBins)
        {
            List<ILiteral> items = new List<ILiteral>();
            foreach (int i in allItems)
            {
                items.Add(x[i, b]);
            }
            model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]);
        }

        // Objective.
        LinearExprBuilder obj = LinearExpr.NewBuilder();
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                obj.AddTerm(x[i, b], Values[i]);
            }
        }
        model.Maximize(obj);

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        // Print solution.
        // Check that the problem has a feasible solution.
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
            double TotalWeight = 0.0;
            foreach (int b in allBins)
            {
                double BinWeight = 0.0;
                double BinValue = 0.0;
                Console.WriteLine($"Bin {b}");
                foreach (int i in allItems)
                {
                    if (solver.BooleanValue(x[i, b]))
                    {
                        Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                        BinWeight += Weights[i];
                        BinValue += Values[i];
                    }
                }
                Console.WriteLine("Packed bin weight: " + BinWeight);
                Console.WriteLine("Packed bin value: " + BinValue);
                TotalWeight += BinWeight;
            }
            Console.WriteLine("Total packed weight: " + TotalWeight);
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
        Console.WriteLine($"  branches : {solver.NumBranches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()}s");
    }
}

宣告模型

下列程式碼宣告 CP-SAT 模型。

Python

model = cp_model.CpModel()

C++

CpModelBuilder cp_model;

Java

CpModel model = new CpModel();

C#

CpModel model = new CpModel();

建立資料

下方程式碼會設定問題資料。

Python

data = {}
data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
assert len(data["weights"]) == len(data["values"])
num_items = len(data["weights"])
all_items = range(num_items)

data["bin_capacities"] = [100, 100, 100, 100, 100]
num_bins = len(data["bin_capacities"])
all_bins = range(num_bins)

C++

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 = static_cast<int>(weights.size());
std::vector<int> all_items(num_items);
std::iota(all_items.begin(), all_items.end(), 0);

const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
const int num_bins = static_cast<int>(bin_capacities.size());
std::vector<int> all_bins(num_bins);
std::iota(all_bins.begin(), all_bins.end(), 0);

Java

final int[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
final int[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
final int numItems = weights.length;
final int[] allItems = IntStream.range(0, numItems).toArray();

final int[] binCapacities = {100, 100, 100, 100, 100};
final int numBins = binCapacities.length;
final int[] allBins = IntStream.range(0, numBins).toArray();

C#

int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();

int[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();

costs 陣列對應到費用的「表」將工作站指派給工作，如上所示。

建立變數

下列程式碼會為問題建立二進位整數變數。

Python

# x[i, b] = 1 if item i is packed in bin b.
x = {}
for i in all_items:
    for b in all_bins:
        x[i, b] = model.new_bool_var(f"x_{i}_{b}")

C++

// x[i, b] = 1 if item i is packed in bin b.
std::map<std::tuple<int, int>, BoolVar> x;
for (int i : all_items) {
  for (int b : all_bins) {
    auto key = std::make_tuple(i, b);
    x[key] = cp_model.NewBoolVar().WithName(absl::StrFormat("x_%d_%d", i, b));
  }
}

Java

Literal[][] x = new Literal[numItems][numBins];
for (int i : allItems) {
  for (int b : allBins) {
    x[i][b] = model.newBoolVar("x_" + i + "_" + b);
  }
}

C#

ILiteral[,] x = new ILiteral[NumItems, NumBins];
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        x[i, b] = model.NewBoolVar($"x_{i}_{b}");
    }
}

建立限制

下列程式碼會建立問題限制條件。

Python

# Each item is assigned to at most one bin.
for i in all_items:
    model.add_at_most_one(x[i, b] for b in all_bins)

# The amount packed in each bin cannot exceed its capacity.
for b in all_bins:
    model.add(
        sum(x[i, b] * data["weights"][i] for i in all_items)
        <= data["bin_capacities"][b]
    )

C++

// Each item is assigned to at most one bin.
for (int i : all_items) {
  std::vector<BoolVar> copies;
  for (int b : all_bins) {
    copies.push_back(x[std::make_tuple(i, b)]);
  }
  cp_model.AddAtMostOne(copies);
}

// The amount packed in each bin cannot exceed its capacity.
for (int b : all_bins) {
  LinearExpr bin_weight;
  for (int i : all_items) {
    bin_weight += x[std::make_tuple(i, b)] * weights[i];
  }
  cp_model.AddLessOrEqual(bin_weight, bin_capacities[b]);
}

Java

// Each item is assigned to at most one bin.
for (int i : allItems) {
  List<Literal> bins = new ArrayList<>();
  for (int b : allBins) {
    bins.add(x[i][b]);
  }
  model.addAtMostOne(bins);
}

// The amount packed in each bin cannot exceed its capacity.
for (int b : allBins) {
  LinearExprBuilder load = LinearExpr.newBuilder();
  for (int i : allItems) {
    load.addTerm(x[i][b], weights[i]);
  }
  model.addLessOrEqual(load, binCapacities[b]);
}

C#

// Each item is assigned to at most one bin.
foreach (int i in allItems)
{
    List<ILiteral> literals = new List<ILiteral>();
    foreach (int b in allBins)
    {
        literals.Add(x[i, b]);
    }
    model.AddAtMostOne(literals);
}

// The amount packed in each bin cannot exceed its capacity.
foreach (int b in allBins)
{
    List<ILiteral> items = new List<ILiteral>();
    foreach (int i in allItems)
    {
        items.Add(x[i, b]);
    }
    model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]);
}

建立目標函式

下列程式碼會建立問題的目標函式。

Python

# maximize total value of packed items.
objective = []
for i in all_items:
    for b in all_bins:
        objective.append(cp_model.LinearExpr.term(x[i, b], data["values"][i]))
model.maximize(cp_model.LinearExpr.sum(objective))

C++

// Maximize total value of packed items.
LinearExpr objective;
for (int i : all_items) {
  for (int b : all_bins) {
    objective += x[std::make_tuple(i, b)] * values[i];
  }
}
cp_model.Maximize(objective);

Java

// Maximize total value of packed items.
LinearExprBuilder obj = LinearExpr.newBuilder();
for (int i : allItems) {
  for (int b : allBins) {
    obj.addTerm(x[i][b], values[i]);
  }
}
model.maximize(obj);

C#

LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int i in allItems)
{
    foreach (int b in allBins)
    {
        obj.AddTerm(x[i, b], Values[i]);
    }
}
model.Maximize(obj);

目標函式的值就是指派給該事件的所有變數的總費用。求出題。

叫用解題工具

下列程式碼會叫用解題工具。

Python

solver = cp_model.CpSolver()
status = solver.solve(model)

C++

const CpSolverResponse response = Solve(cp_model.Build());

Java

CpSolver solver = new CpSolver();
final CpSolverStatus status = solver.solve(model);

C#

CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);

列印解決方案

下列程式碼會顯示問題的解決方案。

Python

if status == cp_model.OPTIMAL:
    print(f"Total packed value: {solver.objective_value}")
    total_weight = 0
    for b in all_bins:
        print(f"Bin {b}")
        bin_weight = 0
        bin_value = 0
        for i in all_items:
            if solver.value(x[i, b]) > 0:
                print(
                    f'Item:{i} weight:{data["weights"][i]} value:{data["values"][i]}'
                )
                bin_weight += data["weights"][i]
                bin_value += data["values"][i]
        print(f"Packed bin weight: {bin_weight}")
        print(f"Packed bin value: {bin_value}\n")
        total_weight += bin_weight
    print(f"Total packed weight: {total_weight}")
else:
    print("The problem does not have an optimal solution.")

C++

if (response.status() == CpSolverStatus::OPTIMAL ||
    response.status() == CpSolverStatus::FEASIBLE) {
  LOG(INFO) << "Total packed value: " << response.objective_value();
  double total_weight = 0.0;
  for (int b : all_bins) {
    LOG(INFO) << "Bin " << b;
    double bin_weight = 0.0;
    double bin_value = 0.0;
    for (int i : all_items) {
      auto key = std::make_tuple(i, b);
      if (SolutionIntegerValue(response, x[key]) > 0) {
        LOG(INFO) << "Item " << i << " weight: " << weights[i]
                  << " value: " << values[i];
        bin_weight += weights[i];
        bin_value += values[i];
      }
    }
    LOG(INFO) << "Packed bin weight: " << bin_weight;
    LOG(INFO) << "Packed bin value: " << bin_value;
    total_weight += bin_weight;
  }
  LOG(INFO) << "Total packed weight: " << total_weight;
} else {
  LOG(INFO) << "The problem does not have an optimal solution.";
}

Java

// Check that the problem has an optimal solution.
if (status == CpSolverStatus.OPTIMAL) {
  System.out.println("Total packed value: " + solver.objectiveValue());
  long totalWeight = 0;
  for (int b : allBins) {
    long binWeight = 0;
    long binValue = 0;
    System.out.println("Bin " + b);
    for (int i : allItems) {
      if (solver.booleanValue(x[i][b])) {
        System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]);
        binWeight += weights[i];
        binValue += values[i];
      }
    }
    System.out.println("Packed bin weight: " + binWeight);
    System.out.println("Packed bin value: " + binValue);
    totalWeight += binWeight;
  }
  System.out.println("Total packed weight: " + totalWeight);
} else {
  System.err.println("The problem does not have an optimal solution.");
}

C#

// Check that the problem has a feasible solution.
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
    Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
    double TotalWeight = 0.0;
    foreach (int b in allBins)
    {
        double BinWeight = 0.0;
        double BinValue = 0.0;
        Console.WriteLine($"Bin {b}");
        foreach (int i in allItems)
        {
            if (solver.BooleanValue(x[i, b]))
            {
                Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                BinWeight += Weights[i];
                BinValue += Values[i];
            }
        }
        Console.WriteLine("Packed bin weight: " + BinWeight);
        Console.WriteLine("Packed bin value: " + BinValue);
        TotalWeight += BinWeight;
    }
    Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
    Console.WriteLine("No solution found.");
}

以下是程式的輸出內容。

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

完成計畫

以下是 CP-SAT 解決方案的完整計畫。

Python

"""Solves a multiple knapsack problem using the CP-SAT solver."""
from ortools.sat.python import cp_model


def main() -> None:
    data = {}
    data["weights"] = [48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36]
    data["values"] = [10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25]
    assert len(data["weights"]) == len(data["values"])
    num_items = len(data["weights"])
    all_items = range(num_items)

    data["bin_capacities"] = [100, 100, 100, 100, 100]
    num_bins = len(data["bin_capacities"])
    all_bins = range(num_bins)

    model = cp_model.CpModel()

    # Variables.
    # x[i, b] = 1 if item i is packed in bin b.
    x = {}
    for i in all_items:
        for b in all_bins:
            x[i, b] = model.new_bool_var(f"x_{i}_{b}")

    # Constraints.
    # Each item is assigned to at most one bin.
    for i in all_items:
        model.add_at_most_one(x[i, b] for b in all_bins)

    # The amount packed in each bin cannot exceed its capacity.
    for b in all_bins:
        model.add(
            sum(x[i, b] * data["weights"][i] for i in all_items)
            <= data["bin_capacities"][b]
        )

    # Objective.
    # maximize total value of packed items.
    objective = []
    for i in all_items:
        for b in all_bins:
            objective.append(cp_model.LinearExpr.term(x[i, b], data["values"][i]))
    model.maximize(cp_model.LinearExpr.sum(objective))

    solver = cp_model.CpSolver()
    status = solver.solve(model)

    if status == cp_model.OPTIMAL:
        print(f"Total packed value: {solver.objective_value}")
        total_weight = 0
        for b in all_bins:
            print(f"Bin {b}")
            bin_weight = 0
            bin_value = 0
            for i in all_items:
                if solver.value(x[i, b]) > 0:
                    print(
                        f'Item:{i} weight:{data["weights"][i]} value:{data["values"][i]}'
                    )
                    bin_weight += data["weights"][i]
                    bin_value += data["values"][i]
            print(f"Packed bin weight: {bin_weight}")
            print(f"Packed bin value: {bin_value}\n")
            total_weight += bin_weight
        print(f"Total packed weight: {total_weight}")
    else:
        print("The problem does not have an optimal solution.")


if __name__ == "__main__":
    main()

C++

// Solves a multiple knapsack problem using the CP-SAT solver.
#include <stdlib.h>

#include <map>
#include <numeric>
#include <tuple>
#include <vector>

#include "absl/strings/str_format.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"

namespace operations_research {
namespace sat {

void MultipleKnapsackSat() {
  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 = static_cast<int>(weights.size());
  std::vector<int> all_items(num_items);
  std::iota(all_items.begin(), all_items.end(), 0);

  const std::vector<int> bin_capacities = {{100, 100, 100, 100, 100}};
  const int num_bins = static_cast<int>(bin_capacities.size());
  std::vector<int> all_bins(num_bins);
  std::iota(all_bins.begin(), all_bins.end(), 0);

  CpModelBuilder cp_model;

  // Variables.
  // x[i, b] = 1 if item i is packed in bin b.
  std::map<std::tuple<int, int>, BoolVar> x;
  for (int i : all_items) {
    for (int b : all_bins) {
      auto key = std::make_tuple(i, b);
      x[key] = cp_model.NewBoolVar().WithName(absl::StrFormat("x_%d_%d", i, b));
    }
  }

  // Constraints.
  // Each item is assigned to at most one bin.
  for (int i : all_items) {
    std::vector<BoolVar> copies;
    for (int b : all_bins) {
      copies.push_back(x[std::make_tuple(i, b)]);
    }
    cp_model.AddAtMostOne(copies);
  }

  // The amount packed in each bin cannot exceed its capacity.
  for (int b : all_bins) {
    LinearExpr bin_weight;
    for (int i : all_items) {
      bin_weight += x[std::make_tuple(i, b)] * weights[i];
    }
    cp_model.AddLessOrEqual(bin_weight, bin_capacities[b]);
  }

  // Objective.
  // Maximize total value of packed items.
  LinearExpr objective;
  for (int i : all_items) {
    for (int b : all_bins) {
      objective += x[std::make_tuple(i, b)] * values[i];
    }
  }
  cp_model.Maximize(objective);

  const CpSolverResponse response = Solve(cp_model.Build());

  if (response.status() == CpSolverStatus::OPTIMAL ||
      response.status() == CpSolverStatus::FEASIBLE) {
    LOG(INFO) << "Total packed value: " << response.objective_value();
    double total_weight = 0.0;
    for (int b : all_bins) {
      LOG(INFO) << "Bin " << b;
      double bin_weight = 0.0;
      double bin_value = 0.0;
      for (int i : all_items) {
        auto key = std::make_tuple(i, b);
        if (SolutionIntegerValue(response, x[key]) > 0) {
          LOG(INFO) << "Item " << i << " weight: " << weights[i]
                    << " value: " << values[i];
          bin_weight += weights[i];
          bin_value += values[i];
        }
      }
      LOG(INFO) << "Packed bin weight: " << bin_weight;
      LOG(INFO) << "Packed bin value: " << bin_value;
      total_weight += bin_weight;
    }
    LOG(INFO) << "Total packed weight: " << total_weight;
  } else {
    LOG(INFO) << "The problem does not have an optimal solution.";
  }

  // Statistics.
  LOG(INFO) << "Statistics";
  LOG(INFO) << CpSolverResponseStats(response);
}
}  // namespace sat
}  // namespace operations_research

int main() {
  operations_research::sat::MultipleKnapsackSat();
  return EXIT_SUCCESS;
}

Java

// Solves a multiple knapsack problem using the CP-SAT solver.
package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

/** Sample showing how to solve a multiple knapsack problem. */
public class MultipleKnapsackSat {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Instantiate the data problem.
    final int[] weights = {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
    final int[] values = {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
    final int numItems = weights.length;
    final int[] allItems = IntStream.range(0, numItems).toArray();

    final int[] binCapacities = {100, 100, 100, 100, 100};
    final int numBins = binCapacities.length;
    final int[] allBins = IntStream.range(0, numBins).toArray();

    CpModel model = new CpModel();

    // Variables.
    Literal[][] x = new Literal[numItems][numBins];
    for (int i : allItems) {
      for (int b : allBins) {
        x[i][b] = model.newBoolVar("x_" + i + "_" + b);
      }
    }

    // Constraints.
    // Each item is assigned to at most one bin.
    for (int i : allItems) {
      List<Literal> bins = new ArrayList<>();
      for (int b : allBins) {
        bins.add(x[i][b]);
      }
      model.addAtMostOne(bins);
    }

    // The amount packed in each bin cannot exceed its capacity.
    for (int b : allBins) {
      LinearExprBuilder load = LinearExpr.newBuilder();
      for (int i : allItems) {
        load.addTerm(x[i][b], weights[i]);
      }
      model.addLessOrEqual(load, binCapacities[b]);
    }

    // Objective.
    // Maximize total value of packed items.
    LinearExprBuilder obj = LinearExpr.newBuilder();
    for (int i : allItems) {
      for (int b : allBins) {
        obj.addTerm(x[i][b], values[i]);
      }
    }
    model.maximize(obj);

    CpSolver solver = new CpSolver();
    final CpSolverStatus status = solver.solve(model);

    // Check that the problem has an optimal solution.
    if (status == CpSolverStatus.OPTIMAL) {
      System.out.println("Total packed value: " + solver.objectiveValue());
      long totalWeight = 0;
      for (int b : allBins) {
        long binWeight = 0;
        long binValue = 0;
        System.out.println("Bin " + b);
        for (int i : allItems) {
          if (solver.booleanValue(x[i][b])) {
            System.out.println("Item " + i + " weight: " + weights[i] + " value: " + values[i]);
            binWeight += weights[i];
            binValue += values[i];
          }
        }
        System.out.println("Packed bin weight: " + binWeight);
        System.out.println("Packed bin value: " + binValue);
        totalWeight += binWeight;
      }
      System.out.println("Total packed weight: " + totalWeight);
    } else {
      System.err.println("The problem does not have an optimal solution.");
    }
  }

  private MultipleKnapsackSat() {}
}

C#

// Solves a multiple knapsack problem using the CP-SAT solver.
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;

public class MultipleKnapsackSat
{
    public static void Main(String[] args)
    {
        // Instantiate the data problem.
        int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
        int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
        int NumItems = Weights.Length;
        int[] allItems = Enumerable.Range(0, NumItems).ToArray();

        int[] BinCapacities = { 100, 100, 100, 100, 100 };
        int NumBins = BinCapacities.Length;
        int[] allBins = Enumerable.Range(0, NumBins).ToArray();

        // Model.
        CpModel model = new CpModel();

        // Variables.
        ILiteral[,] x = new ILiteral[NumItems, NumBins];
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                x[i, b] = model.NewBoolVar($"x_{i}_{b}");
            }
        }

        // Constraints.
        // Each item is assigned to at most one bin.
        foreach (int i in allItems)
        {
            List<ILiteral> literals = new List<ILiteral>();
            foreach (int b in allBins)
            {
                literals.Add(x[i, b]);
            }
            model.AddAtMostOne(literals);
        }

        // The amount packed in each bin cannot exceed its capacity.
        foreach (int b in allBins)
        {
            List<ILiteral> items = new List<ILiteral>();
            foreach (int i in allItems)
            {
                items.Add(x[i, b]);
            }
            model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]);
        }

        // Objective.
        LinearExprBuilder obj = LinearExpr.NewBuilder();
        foreach (int i in allItems)
        {
            foreach (int b in allBins)
            {
                obj.AddTerm(x[i, b], Values[i]);
            }
        }
        model.Maximize(obj);

        // Solve
        CpSolver solver = new CpSolver();
        CpSolverStatus status = solver.Solve(model);

        // Print solution.
        // Check that the problem has a feasible solution.
        if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
        {
            Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
            double TotalWeight = 0.0;
            foreach (int b in allBins)
            {
                double BinWeight = 0.0;
                double BinValue = 0.0;
                Console.WriteLine($"Bin {b}");
                foreach (int i in allItems)
                {
                    if (solver.BooleanValue(x[i, b]))
                    {
                        Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
                        BinWeight += Weights[i];
                        BinValue += Values[i];
                    }
                }
                Console.WriteLine("Packed bin weight: " + BinWeight);
                Console.WriteLine("Packed bin value: " + BinValue);
                TotalWeight += BinWeight;
            }
            Console.WriteLine("Total packed weight: " + TotalWeight);
        }
        else
        {
            Console.WriteLine("No solution found.");
        }

        Console.WriteLine("Statistics");
        Console.WriteLine($"  conflicts: {solver.NumConflicts()}");
        Console.WriteLine($"  branches : {solver.NumBranches()}");
        Console.WriteLine($"  wall time: {solver.WallTime()}s");
    }
}