W tej sekcji pokazujemy, jak rozwiązać problem z wieloma psikusami używając zarówno rozwiązania MIP, jak i CP-SAT. W tym przypadku kontenery często określa się jako pojemniki, a nie jako niż plecaki.
Następny przykład pokazuje, jak znaleźć optymalny sposób na spakowanie produktów do pięciu pojemników.
Przykład
Tak jak w poprzednim przykładzie, zaczynasz od parametru zbiór elementów o różnej wadze i wartościach. Problem polega na zapakowaniu podzbioru produktów do pięciu pojemników, z których każdy może pomieścić do 100 osób, aby łączna wartość zamówienia była maksymalna.
W kolejnych sekcjach przedstawiamy sekcje programów, które pomagają rozwiązać ten problem. Pełną listę programów znajdziesz w artykule Ukończenie programów.
Rozwiązanie MIP
W sekcjach poniżej opisano, jak rozwiązać problem za pomocą Kod MPSolver.
Zaimportuj biblioteki
Poniższy kod importuje wymagane biblioteki.
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;
Tworzenie danych
Poniższy kod tworzy dane dotyczące problemu.
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();Dane te obejmują:
weights: wektor zawierający wagi elementów.values: wektor zawierający wartości elementów.capacities: wektor zawierający pojemności pojemników.
W tym przykładzie wszystkie pojemniki mają taką samą pojemność, ale nie musi to być prawda i ogólnie.
Deklarowanie rozwiązania MIP
Poniższy kod deklaruje rozwiązanie 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; }
Tworzenie zmiennych
Poniższy kod tworzy zmienne związane z tym problemem.
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}");
}
}Każda zmienna x[(i, j)] to zmienna 0–1, gdzie i to element, a j to przedział. W
rozwiązanie, x[(i, j)] będzie mieć wartość 1, jeśli element i znajduje się w koszyku j, a wartość 0
w przeciwnym razie.
Zdefiniuj ograniczenia
Ograniczenia tego problemu definiuje się za pomocą tego kodu:
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]); } }
Ograniczenia są następujące:
- Każdy element można umieścić w maksymalnie jednym koszyku. To ograniczenie jest ustawiane przez
wymaganie, aby suma
x[i, j]we wszystkich przedziałachjbyła mniejsza lub równa do 1. - Łączna waga zapakowana w każdym pojemniku nie może przekroczyć jego pojemności. Ten
jest ustawiane przez wymaganie sumy ciężarów elementów umieszczonych w koszyku
jmusi być mniejsza od pojemności kontenera lub jej równa.
Określ cel
Poniższy kod definiuje funkcję celu dla zadania, którą jest łączna wartość zapakowanych produktów.
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();
Pamiętaj, że funkcja x[i, j] * data['values'][i] dodaje wartość elementu i do
jeśli element znajduje się w koszyku j. Jeśli moduł i nie został umieszczony w żadnym zasobniku,
która nie przyczynia się do realizacji celu.
Wywołaj rozwiązanie
Następujący kod wywołuje rozwiązanie.
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();
Wydrukuj rozwiązanie
Poniższy kod wydrukuje rozwiązanie problemu.
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!"); }
W przypadku każdego przedziału kod wyświetla umieszczone w nim elementy oraz wartość całkowitą i wagę. Kod wyświetla również ogólną łączną wartość waga zapakowanych produktów.
Po uruchomieniu programu wyświetli się następujące dane wyjściowe.
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
Kompletne programy
Poniżej znajduje się pełna treść programów dla wielu organizacji.
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!"); } } }
Rozwiązanie CP SAT
W sekcjach poniżej opisano, jak rozwiązać ten problem za pomocą rozwiązania CP-SAT.
Zaimportuj biblioteki
Poniższy kod importuje wymagane biblioteki.
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"); } }
Deklarowanie modelu
Poniższy kod deklaruje model CP-SAT.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Tworzenie danych
Poniższy kod konfiguruje dane związane z problemem.
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();Tablica costs odpowiada tabeli kosztów
do przypisywania pracowników do zadań.
Tworzenie zmiennych
Następujący kod tworzy dla zadania zmienne binarne z liczbami całkowitymi.
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}");
}
}Tworzenie ograniczeń
Następujący kod tworzy ograniczenia dla tego problemu.
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]); }
Utwórz funkcję celu
Następujący kod tworzy funkcję celu dla zadania.
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);
Wartość funkcji celu to łączny koszt we wszystkich zmiennych, którym przypisano wartość 1 przez rozwiązanie.
Wywołaj rozwiązanie
Następujący kod wywołuje rozwiązanie.
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);
Wydrukuj rozwiązanie
Poniższy kod wydrukuje rozwiązanie problemu.
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."); }
Oto dane wyjściowe programu.
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
Kompletne programy
Oto kompletne programy dotyczące rozwiązania 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"); } }