**Proyecto 2**....Bin packing "Empacado de contenedores"

DESCRIPCION: 
 En el  problema de empacado de contenedores, los objetos deben ser envasados en un numero finito de cubos de capacidad, minimizando el uso de contenedores utilizados.
Existen variaciones de muchos de este problema, como en 2D de embalaje, de embalaje lineal, en peso, embalaje, empaquetado por el costo, y así sucesivamente,
lo tratare de comprender y de hacer de acuerdo al espacio de contenedor declaradas por mi, calculando la cantidad maxima de articulos que se pueden guardar sin riesgos.

 

DEFINICION MATEMATICA:

Dado el tamaño bin V, y una lista @1...@n, de tamaños de los articulos para empacar, encontrar un numero entero A-A particion de

 de tal manera que

para todos

UNA SOLUCION OPTIMA SI TIENE B-MINIMO, El B-valor, para una solucion optima se denota OPT.



EJEMPLO DE INSTANCIA, SOLUCION OPTIMA:
El algoritmo del proceso es en orden arbitrario, para cada objeto, los intentos de colocar el objeto en la primera bandeja que puede albergar el objeto. Si no se encuentra bin, se abre una nueva carpeta y pone el objeto en el inicio de nuevo.

Consigue un factor de aproximación de 2.


PROBLEMA DE DECISION:Es imposible para 2 contenedores de estar en la mayoría de la mitad. La razón es que si en algún momento fue un cubo en la mayoría de la mitad, lo que significa que tiene al menos un espacio de V / 2, el algoritmo no se abre una nueva carpeta para cualquier elemento cuyo tamaño es en la mayoría de V / 2. Sólo después de la bandeja se llena con más de V / 2 o si un elemento con un tamaño mayor que V / 2 llega, el algoritmo se puede abrir una nueva carpeta.


Se tiene que verificar, si los objeto que necesito guardar, equivalen a menos de la cantidad  del espacio del contenedor.
OB <= MDE
OB= objetos, mientras que MDE se define como la mitad del espacio del contenedor.


ALGORITMO DE DECISION:
Se calcula si la cantidad total de dimension de los articulos es menor o igual a la dimension total de un contenedor.
Pidiendole al usuario las cantidades reales, y haciendo las operaciones con las funciones adecuadas


Explicar la COMPLEJIDAD ASINTOTICA:
La cota superior asintótica tiene gran importancia en Teoría de la complejidad computacional a la hora de definir las clases de complejidad.

f(x)=O(g(x))A pesar de que contenedores(g(x)) está definido como un conjunto, se acostumbra escribir  f(x)=O(g(x)) en lugar de f(x)∈O(g(x)). Muchas veces también se habla de una función nombrando únicamente su expresión, como en x² en lugar de h(x)=x², siempre que esté claro cual es el parámetro de la función dentro de la expresión. En la gráfica se da un ejemplo esquemático de como se comporta cg(x) con respecto a f(x) cuando x tiende a infinito.

La cota ajustada asintótica (notación Θ) tiene relación con las cotas asintóticas superior e inferior (notación Ω):
f(x) = Θ(g(x)) si y solo si f(x) = O(g(x)) y f(x) = Ω(x)
Esto quiere decir que se pueden guardar la cantidad maxima de articulos, sin rebasar el espacio a utilizar del contenedor.



El problema de desicion pertenece a P y a  NP,
puesto que los algoritmos recuersivos, se puedes hacer iterativos, con una  solucion mas optima, sin embargo, los iterativos, no se pueden hacer recursivos, ya que intervienen mas aspectors, y en lugar de hacerlos mas faciles de entender, se convierten en mas complejos, disminuyendo la simplicidad que se busca.

Si, NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P.
La razón es que de tenerse una solución polinómica para un problema de NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico (y por lo tanto, si se demuestra que para un problema NP-completo no existe solución en tiempo polinómico, ninguno de los problemas NP tendrá solución).



Existen varias respuestas de desicion, pero la que es mas efectiva, es la de relacionar la capacidad de contenedores, con el espacio que equivalen los articulos en el, para no saturar el contenedor, y usar los menores posibles, esto es:
Que si existe una sumatoria de articulos totales, para un numero minimo de contenedores, se pueda colocar los articulos repartidos equitativamente, en en el numero mas minimo de contenedores?

Argumentar si es Np-duro.
Es NP-Hard, por que hay varias maneras de encontrar una solucion buena, pero en algunos casos esta no es la mejor, la solucion optima, por medio de un algoritmo de ajuste, primero se da la solucion rapida, pero no la optima, colocando cada articulo en el contenedor, y si ya no caben pues en otro.


Se recomienda usar un algoritmo heuristicos para este tipo de problema, pues de este modo, se clasifican los articulos de acuerdo al volumen, y se relacionan con el espacio del contenedor, definiendo que todos los contenedores tienen la misma capacidad.


ALGORITMO PARA EL PROBLEMA DE OPTIMIZACION:
Se define la dimension de los contenedores, tomando en cuenta que todos tienen la misma capacidad y dimension.
Se pide la dimension de cada articulo, en caso de que sea mas de un tipo mismo de articulo
Y la cantidad de articulos a guardar,
Segun al cantidad primaria de articulos a guardar(multiplicandola por la dimension que ocupa, siendo de un mismo tipo), se resta este resultado a la dimension total de un contenedor, si el espacio que le resta al contenedor, y hay mas articulos en espera, se opta, por llenar todo el contenedor, sin triplicar el peso de todos los articulos, al peso del contenedor.


Explicar la complejidad asintotica de este algoritmo tambien.Usualmente se usa la notacion de Landu, para referirnos a las funciones acotadas superiormente, las cuales dependen de otras variables para que sea verdadero lo que se define:

 
Una contenedoresf(x) pertenece a articulos (g(x)) cuando existe una constante positiva c tal que a partir de una cantidad de articulos x0, f(x) no sobrepasa a contenedores(x). Quiere decir que la función f es inferior a g a partir de un valor dado salvo por un factor constante.