Phần này trình bày cách giải bài tập về ba lô cho nhiều loại ba lô bằng cách dùng cả trình giải MIP và trình giải CP-SAT. Trong trường hợp này, chúng ta thường gọi các vùng chứa là thùng, thay vì cả ba lô.
Ví dụ tiếp theo cho thấy cách tìm ra cách tối ưu để đóng gói các mặt hàng vào năm thùng.
Ví dụ:
Như trong ví dụ trước, bạn bắt đầu bằng tập hợp các mục có trọng số và giá trị khác nhau. Vấn đề là việc đóng gói thành năm thùng, mỗi thùng có sức chứa tối đa là 100, sao cho tổng giá trị được đóng gói là giá trị tối đa.
Các phần sau đây trình bày các phần của chương trình giải quyết vấn đề này. Để xem các chương trình đầy đủ, hãy xem phần Hoàn thành chương trình.
Giải pháp MIP
Các phần sau đây mô tả cách giải bài tập bằng cách sử dụng Trình bao bọc MPSolver.
Nhập thư viện
Mã sau đây nhập các thư viện bắt buộc.
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;
Tạo dữ liệu
Mã sau đây sẽ tạo dữ liệu cho bài toán này.
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();Dữ liệu này bao gồm:
weights: Vectơ chứa trọng số của các mục.values: Vectơ chứa giá trị của các mục.capacities: Một vectơ chứa dung lượng của các thùng.
Trong ví dụ này, tất cả các thùng đều có cùng sức chứa, nhưng điều đó không cần phải đúng nói chung.
Khai báo trình giải mã MIP
Mã sau đây khai báo trình giải 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; }
Tạo biến
Mã sau đây sẽ tạo các biến cho bài toán này.
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}");
}
}Mỗi x[(i, j)] là một biến 0-1, trong đó i là một mục và j là một thùng. Ngang bằng
giải pháp, x[(i, j)] sẽ là 1 nếu mục i được đặt vào thùng j và 0
nếu không.
Xác định các điều kiện ràng buộc
Đoạn mã sau đây xác định các quy tắc ràng buộc cho bài toán này:
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]); } }
Có các quy tắc ràng buộc như sau:
- Bạn có thể cho mỗi mục vào tối đa một thùng. Hạn chế này được đặt bởi
yêu cầu tổng của
x[i, j]trên tất cả các thùngjphải nhỏ hơn hoặc bằng đến 1. - Tổng trọng lượng đóng gói trong mỗi thùng không được vượt quá sức chứa của thùng. Chiến dịch này
quy tắc ràng buộc được đặt bằng cách yêu cầu tổng trọng số của các mục được đặt vào thùng
jphải nhỏ hơn hoặc bằng sức chứa của thùng.
Xác định mục tiêu
Mã sau đây xác định hàm mục tiêu của bài toán, đó là hàm tổng giá trị của các mặt hàng đóng gói.
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();
Lưu ý rằng x[i, j] * data['values'][i] sẽ thêm giá trị của mục i vào
mục tiêu nếu mục được đặt trong thùng j. Nếu i không được đặt vào bất kỳ thùng nào,
không đóng góp vào mục tiêu.
Gọi trình giải
Mã sau đây gọi trình giả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();
In giải pháp
Mã sau đây in giải pháp cho sự cố.
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!"); }
Đối với mỗi thùng, mã sẽ hiển thị các mục được đặt vào thùng đó, cũng như các mục của thùng tổng giá trị và trọng số. Mã này cũng hiển thị tổng giá trị và trọng lượng của các mặt hàng đóng gói.
Khi chạy chương trình, bạn sẽ thấy kết quả sau.
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
Hoàn tất chương trình
Dưới đây là các chương trình hoàn chỉnh cho nhiều loại ba lô.
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!"); } } }
Giải pháp CP SAT
Các phần sau đây mô tả cách dùng trình giải quyết CP-SAT để giải bài tập này.
Nhập thư viện
Mã sau đây nhập các thư viện bắt buộc.
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"); } }
Khai báo mô hình
Mã sau đây khai báo mô hình CP-SAT.
Python
model = cp_model.CpModel()
C++
CpModelBuilder cp_model;
Java
CpModel model = new CpModel();
C#
CpModel model = new CpModel();
Tạo dữ liệu
Mã sau đây thiết lập dữ liệu cho sự cố này.
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();Mảng costs tương ứng với bảng chi phí
để phân công nhân viên vào nhiệm vụ, như đã trình bày ở trên.
Tạo biến
Mã sau đây tạo các biến số nguyên nhị phân cho bài toán này.
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}");
}
}Tạo các quy tắc ràng buộc
Mã sau đây tạo ra các điều kiện ràng buộc cho bài toán này.
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]); }
Tạo hàm mục tiêu
Mã sau đây sẽ tạo hàm mục tiêu cho bài toán này.
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);
Giá trị của hàm mục tiêu là tổng chi phí trên tất cả các biến được chỉ định giá trị 1 theo trình giải.
Gọi trình giải
Mã sau đây gọi trình giải.
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);
In giải pháp
Mã sau đây in giải pháp cho sự cố.
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."); }
Đây là kết quả của chương trình.
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
Hoàn tất chương trình
Dưới đây là các chương trình hoàn chỉnh cho giải pháp 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"); } }