En el problema de la mochila, debes empaquetar un conjunto de elementos, con valores determinados. y tamaños (como pesos o volúmenes), en un contenedor con una capacidad máxima de Google Cloud. Si el tamaño total de los elementos supera la capacidad, no puedes empaquetarlos todos. En ese caso, el problema es elegir un subconjunto de los elementos del máximo total que cabe en el contenedor.
Las siguientes secciones muestran cómo resolver un problema de mochila usando las herramientas OR.
Ejemplo
A continuación, se incluye una representación gráfica del problema de la mochila:
En la animación anterior, se empaquetan los elementos 50 en una papelera. Cada elemento tiene un valor
(el número del elemento) y un peso (aproximadamente proporcional al área de la
elemento).
Se declaró que el contenedor tiene una capacidad de 850. Nuestro objetivo es encontrar el conjunto
de elementos que maximizarán el valor total sin exceder la capacidad.
En las siguientes secciones, se describen programas que resuelven un problema de mochila. Para ver los programas completos, consulta Programas completos.
Importa las bibliotecas
El siguiente código importa las bibliotecas requeridas.
Python
from ortools.algorithms.python import knapsack_solver
C++
#include <algorithm> #include <cstdint> #include <iterator> #include <numeric> #include <sstream> #include <vector> #include "ortools/algorithms/knapsack_solver.h"
Java
import com.google.ortools.Loader; import com.google.ortools.algorithms.KnapsackSolver; import java.util.ArrayList;
C#
using System; using Google.OrTools.Algorithms;
Crea los datos
El siguiente código crea los datos para el problema.
Python
values = [
# fmt:off
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
312
# fmt:on
]
weights = [
# fmt: off
[7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13],
# fmt: on
]
capacities = [850]
C++
std::vector<int64_t> values = {
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600,
38, 48, 147, 78, 256, 63, 17, 120, 164, 432, 35, 92, 110,
22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26, 78, 210,
36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
std::vector<std::vector<int64_t>> weights = {
{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13}};
std::vector<int64_t> capacities = {850};
Java
final long[] values = {360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26,
78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
final long[][] weights = {{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9,
0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 86, 66, 31,
65, 0, 79, 20, 65, 52, 13}};
final long[] capacities = {850};
C#
long[] values = { 360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147, 78,
256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73,
78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312 };
long[,] weights = { { 7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13 } };
long[] capacities = { 850 };
Entre los datos, se incluyen los siguientes:
weights: Es un vector que contiene los pesos de los elementos.values: Es un vector que contiene los valores de los elementos.capacities: Es un vector con una sola entrada, la capacidad de la mochila.
Cómo declarar la herramienta de resolución
El siguiente código declara la resolución de mochila, un solucionador especializado para de mochilas.
Python
solver = knapsack_solver.KnapsackSolver(
knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample",
)
C++
KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");
Java
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");
C#
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "KnapsackExample");
La opción KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER le indica al solucionador
usar el algoritmo de rama y de vinculación para resolver el problema.
Llamar a la herramienta de resolución
El siguiente código llama al solucionador y, luego, imprime la solución.
Python
solver.init(values, weights, capacities)
computed_value = solver.solve()
packed_items = []
packed_weights = []
total_weight = 0
print("Total value =", computed_value)
for i in range(len(values)):
if solver.best_solution_contains(i):
packed_items.append(i)
packed_weights.append(weights[0][i])
total_weight += weights[0][i]
print("Total weight:", total_weight)
print("Packed items:", packed_items)
print("Packed_weights:", packed_weights)
C++
solver.Init(values, weights, capacities);
int64_t computed_value = solver.Solve();
std::vector<int> packed_items;
for (std::size_t i = 0; i < values.size(); ++i) {
if (solver.BestSolutionContains(i)) packed_items.push_back(i);
}
std::ostringstream packed_items_ss;
std::copy(packed_items.begin(), packed_items.end() - 1,
std::ostream_iterator<int>(packed_items_ss, ", "));
packed_items_ss << packed_items.back();
std::vector<int64_t> packed_weights;
packed_weights.reserve(packed_items.size());
for (const auto& it : packed_items) {
packed_weights.push_back(weights[0][it]);
}
std::ostringstream packed_weights_ss;
std::copy(packed_weights.begin(), packed_weights.end() - 1,
std::ostream_iterator<int>(packed_weights_ss, ", "));
packed_weights_ss << packed_weights.back();
int64_t total_weights =
std::accumulate(packed_weights.begin(), packed_weights.end(), int64_t{0});
LOG(INFO) << "Total value: " << computed_value;
LOG(INFO) << "Packed items: {" << packed_items_ss.str() << "}";
LOG(INFO) << "Total weight: " << total_weights;
LOG(INFO) << "Packed weights: {" << packed_weights_ss.str() << "}";
Java
solver.init(values, weights, capacities);
final long computedValue = solver.solve();
ArrayList<Integer> packedItems = new ArrayList<>();
ArrayList<Long> packedWeights = new ArrayList<>();
int totalWeight = 0;
System.out.println("Total value = " + computedValue);
for (int i = 0; i < values.length; i++) {
if (solver.bestSolutionContains(i)) {
packedItems.add(i);
packedWeights.add(weights[0][i]);
totalWeight = (int) (totalWeight + weights[0][i]);
}
}
System.out.println("Total weight: " + totalWeight);
System.out.println("Packed items: " + packedItems);
System.out.println("Packed weights: " + packedWeights);
C#
solver.Init(values, weights, capacities);
long computedValue = solver.Solve();
Console.WriteLine("Optimal Value = " + computedValue);
El programa primero inicializa el solucionador y, luego, lo llama
computed_value = solver.Solve()
El valor total de la solución óptima es computed_value, que es igual.
como la ponderación total en este caso. Luego, el programa obtiene los índices de
elementos empaquetados en la solución de la siguiente manera:
packed_items = [x for x in range(0, len(weights[0]))
if solver.BestSolutionContains(x)]
Dado que `solver.BestSolutionContains(x)` muestra `TRUE` si se incluye el elemento x.
En la solución, `pack_items` es una lista de los elementos empaquetados óptimos.
De manera similar, los "pesos_paquetes" son los pesos de los elementos empaquetados.
### Resultado del programa
Este es el resultado del programa.
Total value = 7534
Total weight: 850
Packed items: [0, 1, 3, 4, 6, 10, 11, 12, 14, 15, 16, 17, 18, 19, 21, 22, 24, 27, 28, 29, 30, 31,
32, 34, 38, 39, 41, 42, 44, 47, 48, 49]
Packed_weights: [7, 0, 22, 80, 11, 59, 18, 0, 3, 8, 15, 42, 9, 0, 47, 52, 26, 6, 29, 84, 2, 4,
18, 7, 71, 3, 66, 31, 0, 65, 52, 13]
Completar programas
A continuación, se muestran los programas completos que resuelven el problema de la mochila.
Python
from ortools.algorithms.python import knapsack_solver
def main():
# Create the solver.
solver = knapsack_solver.KnapsackSolver(
knapsack_solver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample",
)
values = [
# fmt:off
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28,
87, 73, 78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276,
312
# fmt:on
]
weights = [
# fmt: off
[7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9, 0,
42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71,
3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13],
# fmt: on
]
capacities = [850]
solver.init(values, weights, capacities)
computed_value = solver.solve()
packed_items = []
packed_weights = []
total_weight = 0
print("Total value =", computed_value)
for i in range(len(values)):
if solver.best_solution_contains(i):
packed_items.append(i)
packed_weights.append(weights[0][i])
total_weight += weights[0][i]
print("Total weight:", total_weight)
print("Packed items:", packed_items)
print("Packed_weights:", packed_weights)
if __name__ == "__main__":
main()
C++
#include <algorithm>
#include <cstdint>
#include <iterator>
#include <numeric>
#include <sstream>
#include <vector>
#include "ortools/algorithms/knapsack_solver.h"
namespace operations_research {
void RunKnapsackExample() {
// Instantiate the solver.
KnapsackSolver solver(
KnapsackSolver::KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER,
"KnapsackExample");
std::vector<int64_t> values = {
360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600,
38, 48, 147, 78, 256, 63, 17, 120, 164, 432, 35, 92, 110,
22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26, 78, 210,
36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
std::vector<std::vector<int64_t>> weights = {
{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13}};
std::vector<int64_t> capacities = {850};
solver.Init(values, weights, capacities);
int64_t computed_value = solver.Solve();
// Print solution
std::vector<int> packed_items;
for (std::size_t i = 0; i < values.size(); ++i) {
if (solver.BestSolutionContains(i)) packed_items.push_back(i);
}
std::ostringstream packed_items_ss;
std::copy(packed_items.begin(), packed_items.end() - 1,
std::ostream_iterator<int>(packed_items_ss, ", "));
packed_items_ss << packed_items.back();
std::vector<int64_t> packed_weights;
packed_weights.reserve(packed_items.size());
for (const auto& it : packed_items) {
packed_weights.push_back(weights[0][it]);
}
std::ostringstream packed_weights_ss;
std::copy(packed_weights.begin(), packed_weights.end() - 1,
std::ostream_iterator<int>(packed_weights_ss, ", "));
packed_weights_ss << packed_weights.back();
int64_t total_weights =
std::accumulate(packed_weights.begin(), packed_weights.end(), int64_t{0});
LOG(INFO) << "Total value: " << computed_value;
LOG(INFO) << "Packed items: {" << packed_items_ss.str() << "}";
LOG(INFO) << "Total weight: " << total_weights;
LOG(INFO) << "Packed weights: {" << packed_weights_ss.str() << "}";
}
} // namespace operations_research
int main(int argc, char** argv) {
operations_research::RunKnapsackExample();
return EXIT_SUCCESS;
}
Java
package com.google.ortools.algorithms.samples;
import com.google.ortools.Loader;
import com.google.ortools.algorithms.KnapsackSolver;
import java.util.ArrayList;
/**
* Sample showing how to model using the knapsack solver.
*/
public class Knapsack {
private Knapsack() {}
private static void solve() {
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "test");
final long[] values = {360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147,
78, 256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73, 78, 15, 26,
78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312};
final long[][] weights = {{7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15, 42, 9,
0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56, 7, 29, 93, 44, 71, 3, 86, 66, 31,
65, 0, 79, 20, 65, 52, 13}};
final long[] capacities = {850};
solver.init(values, weights, capacities);
final long computedValue = solver.solve();
ArrayList<Integer> packedItems = new ArrayList<>();
ArrayList<Long> packedWeights = new ArrayList<>();
int totalWeight = 0;
System.out.println("Total value = " + computedValue);
for (int i = 0; i < values.length; i++) {
if (solver.bestSolutionContains(i)) {
packedItems.add(i);
packedWeights.add(weights[0][i]);
totalWeight = (int) (totalWeight + weights[0][i]);
}
}
System.out.println("Total weight: " + totalWeight);
System.out.println("Packed items: " + packedItems);
System.out.println("Packed weights: " + packedWeights);
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
Knapsack.solve();
}
}
C#
using System;
using Google.OrTools.Algorithms;
public class Knapsack
{
static void Main()
{
KnapsackSolver solver = new KnapsackSolver(
KnapsackSolver.SolverType.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER, "KnapsackExample");
long[] values = { 360, 83, 59, 130, 431, 67, 230, 52, 93, 125, 670, 892, 600, 38, 48, 147, 78,
256, 63, 17, 120, 164, 432, 35, 92, 110, 22, 42, 50, 323, 514, 28, 87, 73,
78, 15, 26, 78, 210, 36, 85, 189, 274, 43, 33, 10, 19, 389, 276, 312 };
long[,] weights = { { 7, 0, 30, 22, 80, 94, 11, 81, 70, 64, 59, 18, 0, 36, 3, 8, 15,
42, 9, 0, 42, 47, 52, 32, 26, 48, 55, 6, 29, 84, 2, 4, 18, 56,
7, 29, 93, 44, 71, 3, 86, 66, 31, 65, 0, 79, 20, 65, 52, 13 } };
long[] capacities = { 850 };
solver.Init(values, weights, capacities);
long computedValue = solver.Solve();
Console.WriteLine("Optimal Value = " + computedValue);
}
}