Paso mas corto desde un inicio unico

Paso mas corto desde un inicio unico

José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona

En la teoría de grafos, el problema del camino más corto es el problema de encontrar un camino entre dos vértices (o nodos) en un gráfico de tal manera que la suma de los pesos de sus bordes constituyentes se minimiza.

El problema de encontrar el camino más corto entre dos intersecciones en un mapa de ruta puede ser modelado como un caso especial del problema del camino más corto en los gráficos, donde los vértices corresponden a las intersecciones y los bordes corresponden a los segmentos de carretera, cada uno ponderado por la longitud de la segmento.

Consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínima. Un ejemplo de esto es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representarían las ciudades y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.

El problema del camino más corto puede ser definido para grafos no dirigidos, dirigidos o mixtos. La siguiente es una definición para grafos no dirigidos, en el caso de grafos dirigidos la definición de camino requiere que los vértices adyacentes estén conectados por una apropiada arista dirigida.

Dos vértices son adyacentes cuando poseen una arista común. Un camino en un grafo no dirigido es una secuencia de vértices ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \ldots \times V}$ tal que todo vértice ${\displaystyle v_{i}}$ es adyacente con el vértice ${\displaystyle v_{i+1}}$. Un camino ${\displaystyle P}$ se dice que es de longitud ${\displaystyle n}$ si va desde ${\displaystyle v_{1}}$ hasta ${\displaystyle v_{n}}$.

Sea ${\displaystyle e_{i,j}}$ la arista incidente con los vértices ${\displaystyle v_{i}}$ y ${\displaystyle v_{j}}$. Dada una función de variable real ponderada ${\displaystyle f:E\rightarrow \mathbb {R} }$ y un grafo no dirigido ${\displaystyle G}$, el camino más corto desde ${\displaystyle v}$ hasta ${\displaystyle v'}$ es el camino ${\displaystyle P=(v_{1},v_{2},\ldots ,v_{n})}$ (donde ${\displaystyle v_{1}=v}$ y ${\displaystyle v_{n}=v'}$) sobre todos los posibles ${\displaystyle n}$ que minimiza la suma ${\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).}$ Cuando cada arista en el grafo tiene un peso unitario o ${\displaystyle f:E\rightarrow \{1\}}$, hallar el camino más corto es equivalente a encontrar el camino con menor número de aristas.

El problema es también conocido como el problema de los caminos más cortos entre dos nodos, para diferenciarlo de las siguientes generalizaciones:

• El problema de los caminos más cortos desde un origen, en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.
• El problema de los caminos más cortos con un destino, en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.
• El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo.

Algoritmos

Los algoritmos más importantes para resolver este problema son:

• Algoritmo de Dijkstra, resuelve el problema de los caminos más cortos desde un único vértice origen hasta todos los otros vértices del grafo.
• Algoritmo de Bellman - Ford, resuelve el problema de los caminos más cortos desde un origen si la ponderación de las aristas es negativa.
• Algoritmo de Búsqueda A*, resuelve el problema de los caminos más cortos entre un par de vértices usando la heurística para intentar agilizar la búsqueda.
• Algoritmo de Floyd - Warshall, resuelve el problema de los caminos más cortos entre todos los vértices.
• Algoritmo de Johnson, resuelve el problema de los caminos más cortos entre todos los vértices y puede ser más rápido que el de Floyd-Warshall en grafos de baja densidad.
• Algoritmo de Viterbi, resuelve el problema del camino estocástico más corto con un peso probabilístico adicional en cada vértice.

Usos

Los algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre lugares físicos, como las rutas de conducción en sitios de mapas web como MapQuest o Google Maps. Para estas aplicaciones están disponibles rápidos algoritmos especializados.8​

Si un algoritmo representa una máquina abstracta no determinista como un grafo, donde los vértices describen estados, y las aristas posibles transiciones, el algoritmo del camino más cortos puede ser usado para encontrar una secuencia óptima de decisiones para llegar a un cierto estado final o para establecer límites más bajos en el tiempo necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un puzzle como el Cubo de Rubik y cada arista dirigida corresponde a un simple movimiento o giro, los algoritmos del camino más corto se pueden usar para encontrar la solución que utiliza el menor número posible de movimientos.

En el argot de las telecomunicaciones, a este algoritmo es también conocido como el problema del mínimo retraso, y con frecuencia va ligado con el problema del camino más ancho. Por ejemplo, el algoritmo podría buscar el camino más corto entre los más anchos, o el camino más ancho entre los más cortos.

Una aplicación más coloquial es la teoría de los "Seis grados de separación", a partir de la cual se intenta encontrar el camino más corto entre dos personas cualesquiera.

Otras aplicaciones incluyen la investigación de operaciones, instalaciones y facilidad de diseño, robótica, transporte y el diseño VLSI.

Luces de árbol de costo mínimo

Luces de árbol de costo mínimo

José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona

Árbol recubridor mínimo

Definición de árbol de cubrimiento: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Un árbol de cubrimiento para G  es un árbol libre que conecta todos los vértices en V. El costo de un árbol de cubrimiento es la suma de los costos de las aristas en el árbol.

Definición árbol de cubrimiento de mínimo costo: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Sea A= (V, F) [F  E]  un árbol de cubrimiento para G, A es un árbol de mínimo costo para G si no existe para G otro árbol de cubrimiento cuyo costo sea menor que el costo de A.

Propiedad de los árboles de cubrimiento de mínimo costo: Sea G= (V, E) un grafo conexo con una función de costos definida sobre las aristas. Sea U un subconjunto propio de V [U  V]. Si uv es una arista de menor costo tal que u  U y v  V-U entonces existe un árbol de cubrimiento de mínimo costo que incluye uv como una de sus aristas.

Demostración: Supongamos que no existe para G un árbol de mínimo costo que incluya a uv. Sea  A' un árbol de mínimo costo para G. Como A' es un árbol si añadimos uv a A' entonces introducimos un ciclo en A'. De esto se deduce que existe otra arista u'v' en A' tal que u'  U y v'  V. Si quitamos u'v' de A' entonces eliminamos el ciclo y obtenemos un árbol A cuyo costo no es mayor que el costo de A porque asumimos por hipótesis que costo ( uv ) = costo(u'v'). Ésto entra en contradicción con lo supuesto.

Dado un grafo conexo y no dirigido, un árbol recubridor de ese grafo es un subgrafo que tiene que ser un árbol y contener todos los vértices del grafo inicial. Cada arista tiene asignado un peso proporcional entre ellos, que es un número representativo de algún objeto, distancia, etc.; y se usa para asignar un peso total al árbol recubridor mínimo computando la suma de todos los pesos de las aristas del árbol en cuestión. Un árbol recubridor mínimo o un árbol expandido mínimo es un árbol recubridor que pesa menos o igual que otros árboles recubridores. Todo grafo tiene un bosque recubridor mínimo.

Un ejemplo sería una compañía de cable trazando cable a una nueva vecindad. Si está limitada a trazar el cable por ciertos caminos, entonces se hará un grafo que represente los puntos conectados por esos caminos. Algunos de estos caminos podrán ser más caros que otros, por ser más largos. Estos caminos serían representados por las aristas con mayores pesos. Un árbol recubridor para este grafo sería un subconjunto de estos caminos que no tenga ciclos pero que mantenga conectadas todas las casas. Puede haber más de un árbol recubridor posible. El árbol recubridor mínimo será el de menos coste.

En el caso de un empate, porque podría haber más de un árbol recubridor mínimo; en particular, si todos los pesos son iguales, todo árbol recubridor será mínimo. De todas formas, si cada arista tiene un peso distinto existirá sólo un árbol recubridor mínimo. La demostración de esto es trivial y se puede hacer por inducción. Esto ocurre en muchas situaciones de la realidad, como con la compañía de cable en el ejemplo anterior, donde es extraño que dos caminos tengan exactamente el mismo coste. Esto también se generaliza para los bosques recubridores.

Si los pesos son positivos, el árbol recubridor mínimo es el subgrafo de menor costo posible conectando todos los vértices, ya que los subgrafos que contienen ciclos necesariamente tienen más peso total.

Usos

Una de las aplicaciones más destacadas del árbol mínimo recubridor se encuentra en el ámbito de las telecomunicaciones, por ejemplo, en las redes de comunicación eléctrica, telefónica, etc. Los nodos representarían puntos de consumo eléctrico, teléfonos, aeropuertos o computadoras. Las aristas podrían ser cables de alta tensión, fibra óptica, rutas aéreas, etc.

Dos algoritmos para construir árboles de cubrimiento de mínimo costo para grafos no dirigidos, conexos y con costos sobre las aristas.

Algoritmo de Kruskal [1956]

El algoritmo de Kruskal construye el árbol de mínimo costo haciendo una iteración sobre el conjunto de las aristas del grafo. Se considera primero que el  conjunto de las aristas del árbol a formar está vacío (F= { }).También se considera inicialmente el conjunto de vértices como árboles aislados, componentes conexas por sí mismos del árbol a construir. Entonces en cada paso se halla una arista de mínimo costo que conecte a dos componentes conexas diferentes y se le añade a F, formándose así una nueva componente conexa. Cuando todos los vértices pertenezcan a una misma componente entonces ésta es el árbol de cubrimiento de mínimo costo para el grafo dado.

¿Por qué funciona el algoritmo de Kruskal?

En el algoritmo de Kruskal se considera inicialmente cada vértice como un árbol, una componente conexa por sí mismo. Éstos son además árboles de cubrimiento de mínimo costo para el grafo compuesto solamente por ellos puesto que un vértice es también un grafo. Entonces inicialmente tenemos n (n: número de vértices del grafo inicial) árboles de cubrimiento de mínimo costo, componentes conexas. En cada paso elegimos una arista de menor costo que conecte dos componentes conexas, entonces se forma una nueva componente conexa que es también un árbol de mínimo costo del grafo formado con los vértices de las dos componentes conexas involucradas, puesto que hasta el paso anterior estas componentes eran árboles de mínimo costo y la arista hallada es una de las de menor costo que conecta ambas componentes, no existe otra arista con un costo menor que la elegida que conecte las dos componentes conexas.

Orden del algoritmo de Kruskal [implementación]

Nuestra implementación del algoritmo hace uso de una cola con prioridad para ordenar las aristas antes de comenzar a construir el árbol. Las operaciones de crear, insertar las aristas y ordenar la cola con todas las aristas toma O(e log( e ) ) (e: número de aristas) operaciones. En cada iteración se extrae una arista de la cola con prioridad, acción que toma O( log( e ) ) operaciones. Entonces en el peor de los casos, se da cuando la última arista es una arista de menor costo del árbol, el algoritmo tomará un tiempo de orden O(elog(e)) .

Algoritmo de Prim[1957]

Supongamos V= {1, 2,.., n}. El algoritmo de Prim comienza iniciando el conjunto U en cualquier vértice v  V del grafo, tomemos por ejemplo U= {1}. Entonces se construye el árbol de cubrimiento, añadiendo una arista en cada paso, de la manera siguiente:

En cada paso buscamos la arista de menor costo (u, v) que conecta U y V-U, entonces se añade al conjunto de aristas F E del árbol, y se añade el vértice v  V-U a U.

Se repite el paso 1 hasta que U = V.

¿Por qué funciona el algoritmo de Prim?

Este algoritmo es una aplicación directa de la propiedad de los árboles de cubrimiento de mínimo costo: En el primer paso buscamos una arista de menor costo y el árbol formado hasta el momento es de mínimo costo. De manera inductiva notemos que si hasta el paso n-1 tenemos un árbol de mínimo costo con los vértices de U y las aristas halladas, entonces, añadiendo en el paso n la arista de menor costo que conecta U con V-U, seguiremos teniendo un árbol de mínimo costo en U. En el paso n el conjunto de los vértices del árbol obtenido es igual al conjunto de los vértices del grafo (U = V), luego este árbol es de mínimo costo para el grafo en cuestión.

Orden del algoritmo de Prim [implementación]

Nuestra implementación del algoritmo hace una iteración sobre cada uno de los vértices en V-U y los añade a U hasta que U = V, por aquí tenemos n operaciones  (n: número de vértices). Por cada una de estas operaciones tenemos que hallar una arista de menor costo (u, v) u pertenece a U y v pertenece a V-U, es decir, una arista que una el árbol que se va formando, con los vértices de U y las aristas halladas, a uno de los vértices restantes (V-U). La búsqueda se puede facilitar si desde el principio vamos archivando las aristas de menor costo que conectan a U con los vértices en V-U y en cada paso vamos rectificando, a medida que se le van añadiendo vértices a U. Como en cada paso tenemos que ir rectificando el archivo, esto nos tomará O(n) operaciones en el mejor de los casos. Por tanto, este algoritmo es de orden O(n²).

Comparación entre los algoritmos de Prim y Kruskal

Los algoritmos de Prim y Kruskal toman un tiempo de orden O(n²) y O(elog(e)) respectivamente (n, e: número de vértices y aristas del grafo, respectivamente). Por ésto si el grafo es denso, tiene muchas aristas con respecto a la cantidad de vértices   (e ≈ n² ó e > n²), es aconsejable utilizar el algoritmo de Prim, de lo contrario, 

Modelos óptimos de intercalación

Modelos óptimos de intercalación

José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona

Introducción

Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado. Un ordenamiento es conviene usarlo cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Es importante destacar que existen diferentes técnicas de ordenamiento como lo es; El Método Burbuja, que consiste en comparar pares de valores de llaves; Método Selección, el cual consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo; y por ultimo el Método Intercalación, con el cual se combinan los sub-archivos ordenados en una sola ejecución.

¿Qué es ordenamiento?

Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo a un criterio de ordenamiento. El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia, tal que represente un orden, el cual puede ser numérico, alfabético o alfanumérico, ascendente o descendente.

El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado. El método de ordenamiento es conviene usar Cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Métodos de Ordenamiento

Existen diferentes métodos de ordenamiento de datos como lo son:

1) El Método Burbuja: también conocido como El bubble sort, este método de ordenamiento consiste en comparar pares de valores de llaves, e intercambiarlos si no se encuentran en sus posiciones correctas.

2) Método Selección: consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo con el que está en la primera posición. Luego el segundo mas pequeño, y así sucesivamente hasta ordenar todo el arreglo.

3) Método Intercalación: es en la cual se combinan los sub-archivos ordenados en una sola ejecución. Es un proceso bastante utilizado en sistemas de actualización. También es la única forma que hay para el ordenamiento de archivos, debido a la imposibilidad física de almacenarlos en memoria y a limitaciones en el tiempo, por la cantidad de elementos a ordenar. Existen diferentes tipos de intercalación, de los cuales se puede destacan:

Intercalación Binaria: El algoritmo de ordenación por intercalación simple requiere una exploración o búsqueda secuencial para localizar la posición de un elemento en la sublista ordenada, si en lugar de considerar una búsqueda secuencial se realizara una búsqueda binaria se mejoraría considerablemente el algoritmo y se aumentaría la velocidad de ejecución. Esta modificación se conoce como método de intercalación binaria. Este algoritmo utiliza la técnica de dividir y conquistar por lo tanto, divide al vector y toma un elemento pivote y compara contra él los elementos del vector dividido.

Intercalación Simple: se tienen dos archivos ordenados y se obtiene al final un solo archivo ordenado que contiene los elementos de los dos archivos iniciales. para utilizar el método se inicia con un vector de n posiciones.se comienza con el subíndice i, en la segunda posición incrementando en 1, el elemento del subíndice del vector se elimina de la secuencia y se reinserta en el vector en la posición adecuada.

Intercalación Balanceada: Una intercalación balanceada de m vías utiliza m archivos de entrada y m archivos de de salida. Las k listas ordenadas se distribuyen en forma uniforme en los m archivos de entrada. Se intercalan las listas de cada uno de los archivos, distribuyendo en forma uniforme las listas resultantes en los archivos de salida (de mayor tamaño que las iniciales). Se repite el último paso hasta que un archivo de salida contiene una lista ordenada.

Intercalación Polifásica: Una intercalación polifásica de m vías utiliza 2*m-1 archivos de entrada y 1 archivo de salida. Las k listas se distribuyen en forma no uniforme en los 2*m-1 archivos de entrada.

Se intercalan las listas (de mayor tamaño) en el archivo de salida. El archivo de entrada que primero queda vacío pasa a ser archivo de salida y el archivo de salida pasa a ser de entrada. Se repiten los 2 últimos pasos hasta que un archivo de salida contenga la lista ordenada.

Tipos de ordenamientos:

Los 2 tipos de ordenamientos óptimos según la estructura de datos a utilizar son: los internos y los externos.

Los internos: Son aquellos en que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento sea el mismo, este ordenamiento se aplican cuando el conjunto de datos a clasificar es lo suficientemente pequeño.

Externos: Es cuando los datos a clasificar se encuentran almacenados en archivos, en soportes de almacenamiento masivo (cintas o discos) el tiempo de acceso a lectura y escritura influye en la eficiencia del ordenamiento, por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada.

Búsqueda Binaria

El método de búsqueda binaria divide el total de los elementos en dos, comparando el elemento buscado con el central, en caso de no ser iguales, se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.

Debemos destacar que este método de búsqueda solo funciona con estructuras de datos previamente ordenadas, dividiendo cada vez a la mitad el proceso de búsqueda, lo que hace que el método sea más eficiente.

Ejemplo: si tenemos una estructura ordenada 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría la  posición 4 y el proceso terminaría ya que el elemento buscado no es diferente al que está en la posición central.

Este proceso debe sumar la posición inicial y la final, dividiendo el resultado de la suma entre dos para obtener la posición central generada por el cociente de la división, en este caso es (0+9)/2=4, esta posición se compara con el elemento que estamos buscando y como son iguales la búsqueda se detiene mostrando la posición donde lo encontró.

El problema de la bolsa de papel

El problema de la bolsa de papel

José Padrón C.I 28.462.837 P. no númerica 2 SAIA 2020-1 IUPSM Barcelona

Algoritmo

En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo (del latín, dixit algorithmus y este del griego arithmos, que significa «número», quizá también con influencia del nombre del matemático persa Al-Juarismi) es un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades.2​ Dados un estado inicial y una entrada, siguiendo los pasos sucesivos se llega a un estado final y se obtiene una solución. Los algoritmos son el objeto de estudio de la algoritmia.

El problema de la bolsa de papel (problema de la mochila)

El problema de la bolsa de papel, mayormente conocido como: problema de la mochila (Knaspack problem) es un problema clásico en los problemas denominados COP (por sus siglas en inglés Combinatorial Optimization Problem – Problemas de Optimización Combinatoria) de Inteligencia Artificial. Este problema es considerado NP (Non Probabilistic Problem) ya que existe una combinación exponencial de instancias que, en su totalidad, no pueden ser resueltas. Existen variantes relacionadas con este problema: problema con cantidad de productos limitada, problema con cantidad de productos ilimitada, elección múltiple, elección de un producto de diferentes categorías, como un problema relacionado con el peso de los productos, como un problema relacionado con el monto económico, entre otros. El presente trabajo tiene como objetivo dar un panorama general de este problema y su aplicación en la vida real.

En algoritmia, el problema de la bolsa de papel, mayormente conocido como: problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto finito de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

Se define como, Un conjunto de n artículos donde cada artículo es identificado por nx, con un valor entero px, y un peso wx. El problema consiste en elegir un subconjunto de n artículos maximizando el beneficio obtenido considerando el peso total de los artículos seleccionados, sin exceder la capacidad c de la mochila.

Dorta et al., definen el Problema de la mochila de la siguiente manera: Se dispone de una mochila de capacidad C y de un conjunto de N objetos, donde los objetos son indivisibles. Describen a un objeto k que tiene un beneficio bk y un peso pk, para k = 1,2,…, N. Para los autores, el problema consiste en averiguar qué objetos se pueden insertar en la mochila sin exceder la capacidad total de la misma, obteniendo el máximo beneficio.

Velasco se basa en la definición formal del problema: “Se tiene una determinada instancia de KP con un conjunto de objetos N, que consiste de n objetos j con ganancia pj y peso wj, y una capacidad c. (Usualmente, los valores toman números enteros positivos). El objetivo es seleccionar un subconjunto de N tal que la ganancia total de esos objetos seleccionados es maximizado y el total de los pesos no excede a c”.

El problema de la mochila es uno de los 21 problemas NP-completos de Richard Karp, 

establecidos por el informático teórico en un famoso artículo de 1972. Ha sido intensamente estudiado desde mediados del siglo XX y se hace referencia a él en el año 1897, en un artículo de George Mathews Ballard.2

Si bien la formulación del problema es sencilla, su resolución es más compleja. Algunos algoritmos existentes pueden resolverlo en la práctica para casos de un gran tamaño. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación de operaciones.

Ejemplo

Un muelle tiene un carguero con capacidad de hasta 700 toneladas. El carguero transporta contenedores de diferentes pesos para una determinada ruta. En la ruta actual el carguero puede transportar algunos de los siguientes contenedores:

El analista de la empresa del muelle desea determinar el envío (conjunto de contenedores) que maximiza la carga transportada. Para ello se propone el siguiente modelo de Programación Entera:

Variables de decisión

Función Objetivo: Consiste en maximizar la carga que transportará el carguero.

Restricciones: El peso de la carga transportada no puede exceder la capacidad máxima del carguero.

La solución óptima consiste en transportar los contenedores C1, C2, C3, C4, C8, C9 y C10, con un valor óptimo de 700 (toneladas), es decir, se utiliza la capacidad completa del carguero. Notar que otra solución óptima consiste en transportar los contenedores C1, C3, C4, C5, C6, C7, C8 y C9 lo que reporta un similar valor en la función objetivo.

La solución sería llevar 3 del C, 1 del B y 2 del A