В этом разделе показано, как решить задачу о рюкзаке для нескольких рюкзаков, используя как решатель MIP, так и решатель CP-SAT. В этом случае контейнеры принято называть контейнерами , а не рюкзаками.
В следующем примере показано, как найти оптимальный способ упаковать предметы в пять корзин.
Пример
Как и в предыдущем примере , вы начинаете с набора предметов разного веса и ценности. Проблема состоит в том, чтобы упаковать подмножество предметов в пять контейнеров, каждая из которых имеет максимальную вместимость 100, так, чтобы общая упакованная ценность была максимальной.
В следующих разделах представлены разделы программ, решающих данную проблему. Полные программы см. в разделе Полные программы .
МИП-решение
В следующих разделах описано, как решить проблему с помощью оболочки MPsolver .
Импортируйте библиотеки
Следующий код импортирует необходимые библиотеки.
Питон
from ortools.linear_solver import pywraplp
С++
#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"
Джава
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;
С#
using System; using System.Collections.Generic; using System.Linq; using Google.OrTools.LinearSolver;
Создайте данные
Следующий код создает данные для проблемы.
Питон
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"])С++
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);Джава
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();С#
double[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
double[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();
double[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();Данные включают в себя следующее:
-
weights: вектор, содержащий веса элементов. -
values: вектор, содержащий значения элементов. -
capacities: вектор, содержащий емкости бункеров.
В этом примере все бункеры имеют одинаковую емкость, но в целом это не обязательно так.
Объявить решатель MIP
Следующий код объявляет решатель MIP.
Питон
solver = pywraplp.Solver.CreateSolver("SCIP")
if solver is None:
print("SCIP solver unavailable.")
returnС++
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("SCIP"));
if (!solver) {
LOG(WARNING) << "SCIP solver unavailable.";
return;
}Джава
// 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;
}С#
// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}Создайте переменные
Следующий код создает переменные для проблемы.
Питон
# 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}")С++
// 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));
}
}Джава
MPVariable[][] x = new MPVariable[numItems][numBins];
for (int i : allItems) {
for (int b : allBins) {
x[i][b] = solver.makeBoolVar("x_" + i + "_" + b);
}
}С#
Variable[,] x = new Variable[NumItems, NumBins];
foreach (int i in allItems)
{
foreach (int b in allBins)
{
x[i, b] = solver.MakeBoolVar($"x_{i}_{b}");
}
} Каждый x[(i, j)] — это переменная 0–1, где i — элемент, а j — ячейка. В решении x[(i, j)] будет равно 1, если элемент i помещен в корзину j , и 0 в противном случае.
Определите ограничения
Следующий код определяет ограничения для проблемы:
Питон
# 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]
)С++
// 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]);
}Джава
// 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]);
}
}С#
// 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]);
}
}Ограничения следующие:
- Каждый предмет можно поместить не более чем в одну корзину. Это ограничение устанавливается требованием, чтобы сумма
x[i, j]по всем интерваламjбыла меньше или равна 1. - Общий вес каждого контейнера не может превышать его вместимость. Это ограничение устанавливается требованием, чтобы сумма весов предметов, помещенных в корзину
j, была меньше или равна вместимости корзины.
Определите цель
Следующий код определяет целевую функцию для задачи, которая представляет собой общую стоимость упакованных предметов.
Питон
# 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()С++
// 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);Джава
// 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();С#
Objective objective = solver.Objective();
foreach (int i in allItems)
{
foreach (int b in allBins)
{
objective.SetCoefficient(x[i, b], Values[i]);
}
}
objective.SetMaximization(); Обратите внимание, что x[i, j] * data['values'][i] добавляет значение элемента i к цели, если элемент помещен в корзину j . Если i не помещен ни в одну корзину, его значение не способствует достижению цели.
Вызов решателя
Следующий код вызывает решатель.
Питон
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()С++
const MPSolver::ResultStatus result_status = solver->Solve();
Джава
final MPSolver.ResultStatus status = solver.solve();
С#
Solver.ResultStatus resultStatus = 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 (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.";
}Джава
// 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.");
}С#
// Check that the problem has an optimal solution.
if (resultStatus == Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine($"Total packed value: {solver.Objective().Value()}");
double TotalWeight = 0.0;
foreach (int b in allBins)
{
double BinWeight = 0.0;
double BinValue = 0.0;
Console.WriteLine("Bin " + b);
foreach (int i in allItems)
{
if (x[i, b].SolutionValue() == 1)
{
Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
BinWeight += Weights[i];
BinValue += Values[i];
}
}
Console.WriteLine("Packed bin weight: " + BinWeight);
Console.WriteLine("Packed bin value: " + BinValue);
TotalWeight += BinWeight;
}
Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
Console.WriteLine("The problem does not have an optimal solution!");
}Для каждой корзины код отображает предметы, помещенные в эту корзину, а также общую стоимость и вес корзины. Код также отображает общую стоимость и вес упакованных предметов.
Когда вы запускаете программу, она отображает следующий вывод.
Total packed value: 395.0 Bin 0 Item 3 - weight: 36 value: 50 Item 13 - weight: 36 value: 30 Packed bin weight: 72 Packed bin value: 80 Bin 1 Item 5 - weight: 48 value: 30 Item 7 - weight: 42 value: 40 Packed bin weight: 90 Packed bin value: 70 Bin 2 Item 1 - weight: 30 value: 30 Item 10 - weight: 30 value: 45 Item 14 - weight: 36 value: 25 Packed bin weight: 96 Packed bin value: 100 Bin 3 Item 2 - weight: 42 value: 25 Item 12 - weight: 42 value: 20 Packed bin weight: 84 Packed bin value: 45 Bin 4 Item 4 - weight: 36 value: 35 Item 8 - weight: 36 value: 30 Item 9 - weight: 24 value: 35 Packed bin weight: 96 Packed bin value: 100 Total packed weight: 438
Полные программы
Полные программы для нескольких рюкзаков показаны ниже.
Питон
"""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()С++
// 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;
}Джава
// 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() {}
}С#
// Solve a multiple knapsack problem using a MIP solver.
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.LinearSolver;
public class MultipleKnapsackMip
{
public static void Main()
{
// Instantiate the data problem.
double[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
double[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();
double[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();
// Create the linear solver with the SCIP backend.
Solver solver = Solver.CreateSolver("SCIP");
if (solver is null)
{
return;
}
// Variables.
Variable[,] x = new Variable[NumItems, NumBins];
foreach (int i in allItems)
{
foreach (int b in allBins)
{
x[i, b] = solver.MakeBoolVar($"x_{i}_{b}");
}
}
// Constraints.
// Each item is assigned to at most one bin.
foreach (int i in allItems)
{
Constraint constraint = solver.MakeConstraint(0, 1, "");
foreach (int b in allBins)
{
constraint.SetCoefficient(x[i, b], 1);
}
}
// The amount packed in each bin cannot exceed its capacity.
foreach (int b in allBins)
{
Constraint constraint = solver.MakeConstraint(0, BinCapacities[b], "");
foreach (int i in allItems)
{
constraint.SetCoefficient(x[i, b], Weights[i]);
}
}
// Objective.
Objective objective = solver.Objective();
foreach (int i in allItems)
{
foreach (int b in allBins)
{
objective.SetCoefficient(x[i, b], Values[i]);
}
}
objective.SetMaximization();
Solver.ResultStatus resultStatus = solver.Solve();
// Check that the problem has an optimal solution.
if (resultStatus == Solver.ResultStatus.OPTIMAL)
{
Console.WriteLine($"Total packed value: {solver.Objective().Value()}");
double TotalWeight = 0.0;
foreach (int b in allBins)
{
double BinWeight = 0.0;
double BinValue = 0.0;
Console.WriteLine("Bin " + b);
foreach (int i in allItems)
{
if (x[i, b].SolutionValue() == 1)
{
Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
BinWeight += Weights[i];
BinValue += Values[i];
}
}
Console.WriteLine("Packed bin weight: " + BinWeight);
Console.WriteLine("Packed bin value: " + BinValue);
TotalWeight += BinWeight;
}
Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
Console.WriteLine("The problem does not have an optimal solution!");
}
}
}Решение CP SAT
В следующих разделах описано, как решить проблему с помощью решателя CP-SAT.
Импортируйте библиотеки
Следующий код импортирует необходимые библиотеки.
Питон
from ortools.sat.python import cp_model
С++
#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"
Джава
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;
С#
using System;
using System.Collections.Generic;
using System.Linq;
using Google.OrTools.Sat;
public class MultipleKnapsackSat
{
public static void Main(String[] args)
{
// Instantiate the data problem.
int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();
int[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray();
// Model.
CpModel model = new CpModel();
// Variables.
ILiteral[,] x = new ILiteral[NumItems, NumBins];
foreach (int i in allItems)
{
foreach (int b in allBins)
{
x[i, b] = model.NewBoolVar($"x_{i}_{b}");
}
}
// Constraints.
// Each item is assigned to at most one bin.
foreach (int i in allItems)
{
List<ILiteral> literals = new List<ILiteral>();
foreach (int b in allBins)
{
literals.Add(x[i, b]);
}
model.AddAtMostOne(literals);
}
// The amount packed in each bin cannot exceed its capacity.
foreach (int b in allBins)
{
List<ILiteral> items = new List<ILiteral>();
foreach (int i in allItems)
{
items.Add(x[i, b]);
}
model.Add(LinearExpr.WeightedSum(items, Weights) <= BinCapacities[b]);
}
// Objective.
LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int i in allItems)
{
foreach (int b in allBins)
{
obj.AddTerm(x[i, b], Values[i]);
}
}
model.Maximize(obj);
// Solve
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
// Print solution.
// Check that the problem has a feasible solution.
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
double TotalWeight = 0.0;
foreach (int b in allBins)
{
double BinWeight = 0.0;
double BinValue = 0.0;
Console.WriteLine($"Bin {b}");
foreach (int i in allItems)
{
if (solver.BooleanValue(x[i, b]))
{
Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
BinWeight += Weights[i];
BinValue += Values[i];
}
}
Console.WriteLine("Packed bin weight: " + BinWeight);
Console.WriteLine("Packed bin value: " + BinValue);
TotalWeight += BinWeight;
}
Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
Console.WriteLine("No solution found.");
}
Console.WriteLine("Statistics");
Console.WriteLine($" conflicts: {solver.NumConflicts()}");
Console.WriteLine($" branches : {solver.NumBranches()}");
Console.WriteLine($" wall time: {solver.WallTime()}s");
}
}
Объявить модель
Следующий код объявляет модель CP-SAT.
Питон
model = cp_model.CpModel()
С++
CpModelBuilder cp_model;
Джава
CpModel model = new CpModel();
С#
CpModel model = new CpModel();
Создайте данные
Следующий код настраивает данные для проблемы.
Питон
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)С++
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);Джава
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();С#
int[] Weights = { 48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36 };
int[] Values = { 10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25 };
int NumItems = Weights.Length;
int[] allItems = Enumerable.Range(0, NumItems).ToArray();
int[] BinCapacities = { 100, 100, 100, 100, 100 };
int NumBins = BinCapacities.Length;
int[] allBins = Enumerable.Range(0, NumBins).ToArray(); Массив costs соответствует таблице затрат на назначение работников на задачи, показанной выше.
Создайте переменные
Следующий код создает двоичные целочисленные переменные для решения проблемы.
Питон
# 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}")С++
// 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));
}
}Джава
Literal[][] x = new Literal[numItems][numBins];
for (int i : allItems) {
for (int b : allBins) {
x[i][b] = model.newBoolVar("x_" + i + "_" + b);
}
}С#
ILiteral[,] x = new ILiteral[NumItems, NumBins];
foreach (int i in allItems)
{
foreach (int b in allBins)
{
x[i, b] = model.NewBoolVar($"x_{i}_{b}");
}
}Создайте ограничения
Следующий код создает ограничения для проблемы.
Питон
# 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]
)С++
// 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]);
}Джава
// 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]);
}С#
// 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]);
}Создайте целевую функцию
Следующий код создает целевую функцию для задачи.
Питон
# 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))С++
// 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);Джава
// 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);С#
LinearExprBuilder obj = LinearExpr.NewBuilder();
foreach (int i in allItems)
{
foreach (int b in allBins)
{
obj.AddTerm(x[i, b], Values[i]);
}
}
model.Maximize(obj);Значение целевой функции — это общая стоимость всех переменных, которым решатель присвоил значение 1.
Вызов решателя
Следующий код вызывает решатель.
Питон
solver = cp_model.CpSolver() status = solver.solve(model)
С++
const CpSolverResponse response = Solve(cp_model.Build());
Джава
CpSolver solver = new CpSolver(); final CpSolverStatus status = solver.solve(model);
С#
CpSolver solver = new CpSolver(); CpSolverStatus 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 (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.";
}Джава
// 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.");
}С#
// Check that the problem has a feasible solution.
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
Console.WriteLine($"Total packed value: {solver.ObjectiveValue}");
double TotalWeight = 0.0;
foreach (int b in allBins)
{
double BinWeight = 0.0;
double BinValue = 0.0;
Console.WriteLine($"Bin {b}");
foreach (int i in allItems)
{
if (solver.BooleanValue(x[i, b]))
{
Console.WriteLine($"Item {i} weight: {Weights[i]} values: {Values[i]}");
BinWeight += Weights[i];
BinValue += Values[i];
}
}
Console.WriteLine("Packed bin weight: " + BinWeight);
Console.WriteLine("Packed bin value: " + BinValue);
TotalWeight += BinWeight;
}
Console.WriteLine("Total packed weight: " + TotalWeight);
}
else
{
Console.WriteLine("No solution found.");
}Вот результат работы программы.
Total packed value: 395.0 Bin 0 Item 3 - weight: 36 value: 50 Item 13 - weight: 36 value: 30 Packed bin weight: 72 Packed bin value: 80 Bin 1 Item 5 - weight: 48 value: 30 Item 7 - weight: 42 value: 40 Packed bin weight: 90 Packed bin value: 70 Bin 2 Item 1 - weight: 30 value: 30 Item 10 - weight: 30 value: 45 Item 14 - weight: 36 value: 25 Packed bin weight: 96 Packed bin value: 100 Bin 3 Item 2 - weight: 42 value: 25 Item 12 - weight: 42 value: 20 Packed bin weight: 84 Packed bin value: 45 Bin 4 Item 4 - weight: 36 value: 35 Item 8 - weight: 36 value: 30 Item 9 - weight: 24 value: 35 Packed bin weight: 96 Packed bin value: 100 Total packed weight: 438
Полные программы
Вот полные программы для решения CP-SAT.
Питон
"""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()С++
// 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;
}Джава
// 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() {}
}С#
// 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");
}
}