Recompensa Económica
Hola!
Estoy trabajando en algoritmo de optimización el cual se puede
describir de la siguiente forma:
Sean U un conjunto de N objetos de tamaño Ti unidades cada uno
y sea B una bolsa o recipiente de tamaño También unidades.
Hay que determinar cuantas bolsas B se necesitan para colocar
los N objetos de U. Y hay que colocar los objetos de tal forma que
se requieran el menor numero de bolsas posibles.
Los objetos no se pueden fraccionar.
Por ejemplo un conjunto U de 8 objetos y Tp =5.6 se vería así:
U = {1.3,1.3,1.3,1.3,2.3,4.5,3.5,4.21}
Tb = 5.6
N = 8
Veamos ahora un ejemplo real con 12 elementos:
Sean
U = {2.7,2.7,2.7,2.7,1.7,1.7,1.7, 1.7, 1.7, 1.7, 1.7, 1.7}
Tb = 6.1
N =12
Solución 1.
Supongamos que coloco en la primera bolsa dos objetos de 2.7
unidades, entonces me quedan 0.7 unidades como residuo o espacio
libre en cada una de ellas. Como en este residuo no me cabe ningún
otro objeto, entonces necesitare 2 bolsas para colocar los 4 objetos
de 2.7unidades y a cada bolsa del restara un residuo de 0.7 unidades.
Ahora, en un bolsa me caben 3 objetos de 1.7 unidades, por lo que
necesitare tres bolsas más para colocar los 8 objetos de 1.7 unidades.
A las primeras dos bolsas les quedara un residuo de 1 unidad y a la
tercera un residuo de 2.7 unidades.
En total necesitaré 5 bolsas para colocar todos los objetos de U.
B1={2,7,2,7} R1=0.7
B2={2,7,2,7} R2=0.7
B3={1.7,1.7,1.7} R3=1.0
B4={1.7,1.7,1.7} R4=1.0
B5={1.7,1.7} R5=2.7
Solución 2.
Supongamos ahora que coloco en una bolsa dos objetos de 1.7 unidades
y un objeto de 2.7 unidades, da exactamente 6.1 unidades que es el
tamaño exacto de la bolsa y tengo cero residuo.
Para colocar los 8 objetos de 1.7 unidades necesitare 4 bolsas y
como en cada bolsa va un objeto de 2.7 unidades entonces cubro
también los 4 objetos de 2.7 unidades.
Haciéndolo de esta manera requeriré solo 4 bolsas para colocar
todos los objetos de U, por lo que este acomodo de los objetos es
mejor que el anterior.
B1={1.7,1.7,2,7} R1=0
B2={1.7,1.7,2,7} R2=0
B3={1.7,1.7,2,7} R3=0
B4={1.7,1.7,2,7} R4=0
Estuve investigando y el algoritmo del Problema de la Mochila
sin Fraccionamiento me puede ayudar, el siguiente es el enunciado
del problema de la mochila.
Sean n objetos y una mochila. Para que = 1,2,..., n, el objeto que tiene
un peso positivo porque y un valor positivo vk. La mochila puede llevar
un peso total que no sobrepase P. Se pretende llenar la mochila de
forma que el valor de los objetos transportados sea máximo.
Yo no necesito Vk, esto es, no requiero optimizar por un valor,
solo por el peso, así que el vector V lo hago igual al vector P.
Esto es si P = {1,2,3} entonces V = {1,2,3}
Implemente 3 algoritmos del problema de la mochila en Visual C++ y
funcionan bien, efectivamente, el algoritmo selecciona los objetos
que hacen aprovechar al máximo el espacio, sin embargo para una
corrida de 25 objetos o más el algoritmo tarda más de 1 hora o dar el
resultado, (lo he corrido en un Pentium III a 1 GHZ). Esto hace
inútil al algoritmo.
En esta página se muestran 4 algoritmos del problema de la mochila,
implemente los 3 primeros ya que el cuarto es con fraccionamiento y
no me sirve así.
http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf
El reto.
Se trata de obtener un algoritmo el cual resuelva mi problema en un
tiempo optimo, y con óptimo me refiero a que para un U de
50 a 80 objetos el algoritmo me diga cuales son los objetos
a incluir en un tiempo de 2 o 3 segundos.
No importa que algoritmo se utilice, quizá haya otra manera de
resolverlo sin utilizar el algoritmo del problema de la mochila.
Para más información sobre el problema de la mochila la pueden
obtener de aquí.
http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf
Recompensa $250 USD.
Condiciones.
Entregar
Estoy trabajando en algoritmo de optimización el cual se puede
describir de la siguiente forma:
Sean U un conjunto de N objetos de tamaño Ti unidades cada uno
y sea B una bolsa o recipiente de tamaño También unidades.
Hay que determinar cuantas bolsas B se necesitan para colocar
los N objetos de U. Y hay que colocar los objetos de tal forma que
se requieran el menor numero de bolsas posibles.
Los objetos no se pueden fraccionar.
Por ejemplo un conjunto U de 8 objetos y Tp =5.6 se vería así:
U = {1.3,1.3,1.3,1.3,2.3,4.5,3.5,4.21}
Tb = 5.6
N = 8
Veamos ahora un ejemplo real con 12 elementos:
Sean
U = {2.7,2.7,2.7,2.7,1.7,1.7,1.7, 1.7, 1.7, 1.7, 1.7, 1.7}
Tb = 6.1
N =12
Solución 1.
Supongamos que coloco en la primera bolsa dos objetos de 2.7
unidades, entonces me quedan 0.7 unidades como residuo o espacio
libre en cada una de ellas. Como en este residuo no me cabe ningún
otro objeto, entonces necesitare 2 bolsas para colocar los 4 objetos
de 2.7unidades y a cada bolsa del restara un residuo de 0.7 unidades.
Ahora, en un bolsa me caben 3 objetos de 1.7 unidades, por lo que
necesitare tres bolsas más para colocar los 8 objetos de 1.7 unidades.
A las primeras dos bolsas les quedara un residuo de 1 unidad y a la
tercera un residuo de 2.7 unidades.
En total necesitaré 5 bolsas para colocar todos los objetos de U.
B1={2,7,2,7} R1=0.7
B2={2,7,2,7} R2=0.7
B3={1.7,1.7,1.7} R3=1.0
B4={1.7,1.7,1.7} R4=1.0
B5={1.7,1.7} R5=2.7
Solución 2.
Supongamos ahora que coloco en una bolsa dos objetos de 1.7 unidades
y un objeto de 2.7 unidades, da exactamente 6.1 unidades que es el
tamaño exacto de la bolsa y tengo cero residuo.
Para colocar los 8 objetos de 1.7 unidades necesitare 4 bolsas y
como en cada bolsa va un objeto de 2.7 unidades entonces cubro
también los 4 objetos de 2.7 unidades.
Haciéndolo de esta manera requeriré solo 4 bolsas para colocar
todos los objetos de U, por lo que este acomodo de los objetos es
mejor que el anterior.
B1={1.7,1.7,2,7} R1=0
B2={1.7,1.7,2,7} R2=0
B3={1.7,1.7,2,7} R3=0
B4={1.7,1.7,2,7} R4=0
Estuve investigando y el algoritmo del Problema de la Mochila
sin Fraccionamiento me puede ayudar, el siguiente es el enunciado
del problema de la mochila.
Sean n objetos y una mochila. Para que = 1,2,..., n, el objeto que tiene
un peso positivo porque y un valor positivo vk. La mochila puede llevar
un peso total que no sobrepase P. Se pretende llenar la mochila de
forma que el valor de los objetos transportados sea máximo.
Yo no necesito Vk, esto es, no requiero optimizar por un valor,
solo por el peso, así que el vector V lo hago igual al vector P.
Esto es si P = {1,2,3} entonces V = {1,2,3}
Implemente 3 algoritmos del problema de la mochila en Visual C++ y
funcionan bien, efectivamente, el algoritmo selecciona los objetos
que hacen aprovechar al máximo el espacio, sin embargo para una
corrida de 25 objetos o más el algoritmo tarda más de 1 hora o dar el
resultado, (lo he corrido en un Pentium III a 1 GHZ). Esto hace
inútil al algoritmo.
En esta página se muestran 4 algoritmos del problema de la mochila,
implemente los 3 primeros ya que el cuarto es con fraccionamiento y
no me sirve así.
http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf
El reto.
Se trata de obtener un algoritmo el cual resuelva mi problema en un
tiempo optimo, y con óptimo me refiero a que para un U de
50 a 80 objetos el algoritmo me diga cuales son los objetos
a incluir en un tiempo de 2 o 3 segundos.
No importa que algoritmo se utilice, quizá haya otra manera de
resolverlo sin utilizar el algoritmo del problema de la mochila.
Para más información sobre el problema de la mochila la pueden
obtener de aquí.
http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf
Recompensa $250 USD.
Condiciones.
Entregar
1 respuesta
Respuesta de kieleze
1