El problema de la mochila
El problema de la mochila
Hola!
Estoy trabajando en un algoritmo de los llamados NP-Completos
En particular se llama "el problema de la mochila" el cual consiste en lo
siguiente:
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.
Supondremos que los objetos no se pueden fraccionar.
Expresaremos la solución mediante un vector por de valores 0 ó 1.
Para k = 1,2,...,n, si xk = 1 entonces el objeto k
debe estar en la mochila; si xk = 0 entonces el objeto k no se selecciona.
Matemáticamente, el problema lo podemos enunciar de la siguiente forma:
Encontrar un vector por de n elementos del conjunto {0,1} de forma que:
La sumatoria desde k=1 hasta n de Xk*Vk sea máximo con la restricción:
La sumatoria desde k=1 hasta n de Xk*Pk < P
(Xk quiere decir Vector X subindice k)
He encontardo 3 algoritmos los cuales he implementado en C++ y C++.NET, sin embargo la complejidad
de estos algoritmos es muy alta, para una corrida con 42 elementos tarda horas, lo cual hace
que no lo pueda utilizar. De donde saque esta información (http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf)
Se hacía referencia a un cuarto algoritmo
en donde se mejora la complejidad sin embargo asume que los objetos se pueden fraccionar lo cual no
es mi caso.
Me pregunto si me puedes ayudar a encontrar un algoritmo que resuelva el problema en un
tiempo mucho menor.
A continuación describo el programa en C++ del primer algoritmos, los demás no los pude adjuntar por
problemas de espacio, son muy similares y se pueden ver en http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf
Forma de llamarlo:
int v[43];
int p[43];
int x[43];
int x_mejor[43];
int v_mejor;
int peso;
int n;
v_mejor = -1;
n=42
peso=610
v[0] = 0;//el primer elemento de la matriz no se utiliza
v[1] = 1;
v[2] = 1;
v[3] = 1;
v[4] = 1;
v[5] = 1;
v[6] = 1;
v[7] = 90;
v[8] = 90;
v[9] = 80;
..
..
v[42]=40;
p[0] = 0;//el primer elemento de la matriz no se utiliza
p[1] = 1;
p[2] = 1;
p[3] = 1;
p[4] = 1;
p[5] = 1;
p[6] = 1;
p[7] = 90;
p[8] = 90;
p[9] = 80;
..
..
p[42]=40;
Mochila(v,p,peso,42,1,x,x_mejor,&v_mejor);
Algoritmo 1.
int Mochila(int v[],int p[],int peso,int n,int k, int x[],int x_mejor[],int *v_mejor)
{
int local_peso;
int local_valor;
int i;
x[k] = -1;
while (x[k] < 1)
{
x[k] = x[k] + 1;
local_peso = 0;
for (i=1;i<=k;i++){
local_peso = local_peso + (x * p);
}
if (local_peso <= peso)
{
if (k == n)
{
local_valor = 0;
for (i=1; i<=k;i++){
local_valor = local_valor + (x * v);
}
if (local_valor > *v_mejor)
{
for (i=1;i<=k;i++){
x_mejor = x;
}
*v_mejor = local_valor;
}
}
else if (k < n)
{
Mochila (v, p, peso, n, k + 1, x, x_mejor, v_mejor);
}
}
}
return 0;
}
Hola!
Estoy trabajando en un algoritmo de los llamados NP-Completos
En particular se llama "el problema de la mochila" el cual consiste en lo
siguiente:
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.
Supondremos que los objetos no se pueden fraccionar.
Expresaremos la solución mediante un vector por de valores 0 ó 1.
Para k = 1,2,...,n, si xk = 1 entonces el objeto k
debe estar en la mochila; si xk = 0 entonces el objeto k no se selecciona.
Matemáticamente, el problema lo podemos enunciar de la siguiente forma:
Encontrar un vector por de n elementos del conjunto {0,1} de forma que:
La sumatoria desde k=1 hasta n de Xk*Vk sea máximo con la restricción:
La sumatoria desde k=1 hasta n de Xk*Pk < P
(Xk quiere decir Vector X subindice k)
He encontardo 3 algoritmos los cuales he implementado en C++ y C++.NET, sin embargo la complejidad
de estos algoritmos es muy alta, para una corrida con 42 elementos tarda horas, lo cual hace
que no lo pueda utilizar. De donde saque esta información (http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf)
Se hacía referencia a un cuarto algoritmo
en donde se mejora la complejidad sin embargo asume que los objetos se pueden fraccionar lo cual no
es mi caso.
Me pregunto si me puedes ayudar a encontrar un algoritmo que resuelva el problema en un
tiempo mucho menor.
A continuación describo el programa en C++ del primer algoritmos, los demás no los pude adjuntar por
problemas de espacio, son muy similares y se pueden ver en http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf
Forma de llamarlo:
int v[43];
int p[43];
int x[43];
int x_mejor[43];
int v_mejor;
int peso;
int n;
v_mejor = -1;
n=42
peso=610
v[0] = 0;//el primer elemento de la matriz no se utiliza
v[1] = 1;
v[2] = 1;
v[3] = 1;
v[4] = 1;
v[5] = 1;
v[6] = 1;
v[7] = 90;
v[8] = 90;
v[9] = 80;
..
..
v[42]=40;
p[0] = 0;//el primer elemento de la matriz no se utiliza
p[1] = 1;
p[2] = 1;
p[3] = 1;
p[4] = 1;
p[5] = 1;
p[6] = 1;
p[7] = 90;
p[8] = 90;
p[9] = 80;
..
..
p[42]=40;
Mochila(v,p,peso,42,1,x,x_mejor,&v_mejor);
Algoritmo 1.
int Mochila(int v[],int p[],int peso,int n,int k, int x[],int x_mejor[],int *v_mejor)
{
int local_peso;
int local_valor;
int i;
x[k] = -1;
while (x[k] < 1)
{
x[k] = x[k] + 1;
local_peso = 0;
for (i=1;i<=k;i++){
local_peso = local_peso + (x * p);
}
if (local_peso <= peso)
{
if (k == n)
{
local_valor = 0;
for (i=1; i<=k;i++){
local_valor = local_valor + (x * v);
}
if (local_valor > *v_mejor)
{
for (i=1;i<=k;i++){
x_mejor = x;
}
*v_mejor = local_valor;
}
}
else if (k < n)
{
Mochila (v, p, peso, n, k + 1, x, x_mejor, v_mejor);
}
}
}
return 0;
}
2 respuestas
Respuesta
1
Lo de que tarda horas puede ser el primer algoritmo: ¿Te pasa lo mismo con la version 4?
Yo hice uno basado en "ramifica y poda" ("branch and bound"), pero está en Pascal. Es el siguiente:
Las listas están implementadas como listas enlazadas me parece, pero eso lo puedes cambiar, se entiende perfectamente qué operaciones se necesitan.
ses listas, listaaux;
{
const
N = 4
type vector = array [1..n] of real;
datos = record
v: vector;
valor: real;
end;
}
const
n = 4;
{ vector de pesos }
peso: array [1..n] of real = (1, 1, 4, 10);
{ vector de valores }
vale: array [1..n] of real = (2, 1, 2, 4); { los objetos ya est n ordenados por densidad }
var
sol: datos;
capacidad: real;
procedure inicia(var sol: datos);
{ inicializa la soluci¢n }
var i: integer;
begin
for i := 1 to n do sol.v := 0;
sol.valor := 0
end; { inicia }
procedure pinta(var v: vector);
{ muestra un vector por pantalla }
var i: integer;
begin
for i := 1 to n do write(v:6:3); writeln
end; { pinta }
procedure voraz(p { ¡ndice }: integer; c: real; var sol: datos);
{ hace de cota, calula el valor desde el objeto p hasta el final }
var i: integer;
begin
{ c es la capacidad }
with sol do
begin
{ bucle voraz }
for i := p to n do
if peso <= c then
begin
v := 1; { incluir el objeto }
c := c - peso
end
else
begin
v := c / peso;
c := 0
end;
{ calcular valor conseguido }
valor := 0;
for i := p to n do
valor := valor + v * vale
{ ,ste indica que se puede, por lo menos, conseguir un valor "valor" }
end
end; { voraz }
procedure branch(ob: integer; c: real; d: datos);
var
l, auxl: lista;
i, k: integer;
aux: datos;
begin
listavacia(auxl);
if ob > n then
begin
if d.valor > sol.valor then
sol := d
end
else
begin
listavacia(l);
for i := 0 to 1 do { meter el objeto o no meterlo }
if peso[ob] * i <= c then { generamos los sucesores }
begin
d.v[ob] := i; d.valor := 0;
for k := 1 to ob do
d.valor := d.valor + d.v[k] * vale[k];
aux := d;
voraz(ob+1, c - d.v[ob] * peso[ob], aux);
d.valor := d.valor + aux.valor;
anadeppio(l, d) { insertar sucesor en la lista }
end;
repeat
copia(l, auxl);
d.valor := 0;
while not esvacia(auxl) do { seleccionamos el mejor }
begin
primero(auxl, aux);
resto(auxl, auxl);
if aux.valor <= sol.valor then
borrar(l, aux) { podamos }
else
if aux.valor > d.valor then d := aux
end;
if not esvacia(l) then
begin
borrar(l, d); { ramificamos y podamos }
branch(ob+1, c - d.v[ob] * peso[ob], d)
end
until esvacia(l)
end
end; { branch }
begin
write('capacidad: '); readln(capacidad);
voraz(1, capacidad, sol); writeln(sol.valor:6:3); pinta(sol.v);
inicia(sol);
branch(1, capacidad, sol); writeln(sol.valor:6:3); pinta(sol.v)
end.
Yo hice uno basado en "ramifica y poda" ("branch and bound"), pero está en Pascal. Es el siguiente:
Las listas están implementadas como listas enlazadas me parece, pero eso lo puedes cambiar, se entiende perfectamente qué operaciones se necesitan.
ses listas, listaaux;
{
const
N = 4
type vector = array [1..n] of real;
datos = record
v: vector;
valor: real;
end;
}
const
n = 4;
{ vector de pesos }
peso: array [1..n] of real = (1, 1, 4, 10);
{ vector de valores }
vale: array [1..n] of real = (2, 1, 2, 4); { los objetos ya est n ordenados por densidad }
var
sol: datos;
capacidad: real;
procedure inicia(var sol: datos);
{ inicializa la soluci¢n }
var i: integer;
begin
for i := 1 to n do sol.v := 0;
sol.valor := 0
end; { inicia }
procedure pinta(var v: vector);
{ muestra un vector por pantalla }
var i: integer;
begin
for i := 1 to n do write(v:6:3); writeln
end; { pinta }
procedure voraz(p { ¡ndice }: integer; c: real; var sol: datos);
{ hace de cota, calula el valor desde el objeto p hasta el final }
var i: integer;
begin
{ c es la capacidad }
with sol do
begin
{ bucle voraz }
for i := p to n do
if peso <= c then
begin
v := 1; { incluir el objeto }
c := c - peso
end
else
begin
v := c / peso;
c := 0
end;
{ calcular valor conseguido }
valor := 0;
for i := p to n do
valor := valor + v * vale
{ ,ste indica que se puede, por lo menos, conseguir un valor "valor" }
end
end; { voraz }
procedure branch(ob: integer; c: real; d: datos);
var
l, auxl: lista;
i, k: integer;
aux: datos;
begin
listavacia(auxl);
if ob > n then
begin
if d.valor > sol.valor then
sol := d
end
else
begin
listavacia(l);
for i := 0 to 1 do { meter el objeto o no meterlo }
if peso[ob] * i <= c then { generamos los sucesores }
begin
d.v[ob] := i; d.valor := 0;
for k := 1 to ob do
d.valor := d.valor + d.v[k] * vale[k];
aux := d;
voraz(ob+1, c - d.v[ob] * peso[ob], aux);
d.valor := d.valor + aux.valor;
anadeppio(l, d) { insertar sucesor en la lista }
end;
repeat
copia(l, auxl);
d.valor := 0;
while not esvacia(auxl) do { seleccionamos el mejor }
begin
primero(auxl, aux);
resto(auxl, auxl);
if aux.valor <= sol.valor then
borrar(l, aux) { podamos }
else
if aux.valor > d.valor then d := aux
end;
if not esvacia(l) then
begin
borrar(l, d); { ramificamos y podamos }
branch(ob+1, c - d.v[ob] * peso[ob], d)
end
until esvacia(l)
end
end; { branch }
begin
write('capacidad: '); readln(capacidad);
voraz(1, capacidad, sol); writeln(sol.valor:6:3); pinta(sol.v);
inicia(sol);
branch(1, capacidad, sol); writeln(sol.valor:6:3); pinta(sol.v)
end.
Hola!
Gracias por contestar.
¿Cuándo me preguntas si me pasa lo mismo con el 4, te refieres al documento http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf)?
Lo que pasa es que ese algoritmo no lo he implementado, supuestamente si es más rapido pero asume que los objetos se puden fraccionar, lo cual no me sirve, he implementado los otros 3 algoritmos y todos son muy lentos.
¿Creo qué el algoritmo que me envías en pascal asume que los objetos se pueden fraccionar verdad?, lo asumo por esta linea, si es así no me va a servir.
v := c / peso;
¿Cuánto tarda tu algoritmo para una entrada de 50 elementos?
Necesito un algoritmo que asuma que los objetos no se pueden fraccionar y que para una entrada de 50 elementos me de la respuesta inmediatamente.
Voy a tratar de analizar tu algoritmo sin embargo esta un poco confuso, ¿por ejemplo no se donde terminan los bucles for? , el if tiene begin y end pero donde finalizan los for?
Agradeceré tus comentarios
Gracias por contestar.
¿Cuándo me preguntas si me pasa lo mismo con el 4, te refieres al documento http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf)?
Lo que pasa es que ese algoritmo no lo he implementado, supuestamente si es más rapido pero asume que los objetos se puden fraccionar, lo cual no me sirve, he implementado los otros 3 algoritmos y todos son muy lentos.
¿Creo qué el algoritmo que me envías en pascal asume que los objetos se pueden fraccionar verdad?, lo asumo por esta linea, si es así no me va a servir.
v := c / peso;
¿Cuánto tarda tu algoritmo para una entrada de 50 elementos?
Necesito un algoritmo que asuma que los objetos no se pueden fraccionar y que para una entrada de 50 elementos me de la respuesta inmediatamente.
Voy a tratar de analizar tu algoritmo sin embargo esta un poco confuso, ¿por ejemplo no se donde terminan los bucles for? , el if tiene begin y end pero donde finalizan los for?
Agradeceré tus comentarios
Sí, me refería a la versión 4 de http://www.dlsi.ua.es/asignaturas/pm/prac3-2000.pdf, pero no había leído que era para el problema con fraccionamiento. Y también, mi algoritmo es con fraccionamiento, no te sirve.
El problema de la mochila sin fraccionamiento [snapsack problem] es un problema NP-completo, lo que significa que no tiene solución de tiempo polinomial en el peor caso. Por eso tardan tanto tus programas, son de tiempo exponencial y eso, como probablemente sabes, es lentísimo, aún para problemas de pequeño tamaño.
Cuando ocurre esto tenemos, a mi entender, sólo las siguientes posibilidades:
- Buscar un algoritmo que sea polinomial (al menos que se conozca que sea rápido en la práctica, sin saber su complejidad) pero EN PROMEDIO. --> Yo no conozco ninguno para el problema de la mochila sin fraccionamiento
- Crear un algoritmo eficiente que busque una solución dado un margen a la solución óptima (por ejemplo: error máximo = 20%). Es decir, se trata de dar una solución aproximada. En el caso de la mochila, no se podrá exceder, por supuesto, el peso máximo.
- Utilizar un algoritmo paralelo y utilizar un ordenador multiprocesador o multicomputador. --> Sé que hay un algoritmo para topología del hipercubo para el problema de la mochila sin fraccionamiento (pero yo no lo tengo).
- Una última cosa que se puede hacer es la siguiente. El tiempo que tardan los algoritmos en ejecutarse no sólo depende de la complejidad sino también de la constante multiplicativa. Se trata de mejorar la constante tanto que nos permita utilizar para los problemas de tamaño deseados.
También se pueden combinar varias de estas estrategias.
El problema de la mochila sin fraccionamiento [snapsack problem] es un problema NP-completo, lo que significa que no tiene solución de tiempo polinomial en el peor caso. Por eso tardan tanto tus programas, son de tiempo exponencial y eso, como probablemente sabes, es lentísimo, aún para problemas de pequeño tamaño.
Cuando ocurre esto tenemos, a mi entender, sólo las siguientes posibilidades:
- Buscar un algoritmo que sea polinomial (al menos que se conozca que sea rápido en la práctica, sin saber su complejidad) pero EN PROMEDIO. --> Yo no conozco ninguno para el problema de la mochila sin fraccionamiento
- Crear un algoritmo eficiente que busque una solución dado un margen a la solución óptima (por ejemplo: error máximo = 20%). Es decir, se trata de dar una solución aproximada. En el caso de la mochila, no se podrá exceder, por supuesto, el peso máximo.
- Utilizar un algoritmo paralelo y utilizar un ordenador multiprocesador o multicomputador. --> Sé que hay un algoritmo para topología del hipercubo para el problema de la mochila sin fraccionamiento (pero yo no lo tengo).
- Una última cosa que se puede hacer es la siguiente. El tiempo que tardan los algoritmos en ejecutarse no sólo depende de la complejidad sino también de la constante multiplicativa. Se trata de mejorar la constante tanto que nos permita utilizar para los problemas de tamaño deseados.
También se pueden combinar varias de estas estrategias.
Hola!
Muchas gracias por tu respuesta.
¿Me pregunto si te interesa ayudarme bajo una recompensa económica?, de hecho acabo de poner el post siguiente en el talón publico de C++ con más detalles sobre el problema.
Saludos
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 código fuente implementado en Visual C++ 6.0 o Visual Basic 6.0.
Mis datos
Horacio Torres
[email protected]
Muchas gracias por tu respuesta.
¿Me pregunto si te interesa ayudarme bajo una recompensa económica?, de hecho acabo de poner el post siguiente en el talón publico de C++ con más detalles sobre el problema.
Saludos
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 código fuente implementado en Visual C++ 6.0 o Visual Basic 6.0.
Mis datos
Horacio Torres
[email protected]
Como dije antes, (¿lo dije?) La optimización del código a bajo nivel no servirá de mucho. Y el problema es NP-completo (exponencial para el caso). Por tanto, si necesitas la solución exacta, buscas un milagro (y al que le ocurra, se hará de oro), pues una solución a ese problema, significaría que la solución de todos los problemas NP-completos es posible en tiempo polinomial ¡Casi nada! Este hecho dispararía la Informática a una carrera como no ha pasado desde el mismo descubrimiento del computador. El tema es muy complejo, incluso hay libros sólo dedicados al mismo:
http://www.amazon.com/exec/obidos/ASIN/0471924202/thealgorithmrepo/103-6772389-2849416
Por tanto, he de deducir que ´buscas una solución aproximada. No tengo ni idea de si ese libro tendrá alguno (para aproximar). Creo que lo mejor que puedes hacer es un voraz con backtracking (prog. Dinámica) en la parte final, cuando el nivel de optimalidad especificado no se ha alcanzado (por ejemplo, el nivel de optimalidad sería dividir el peso obtenido con el peso total, lo que representaría el porcentaje del espacio total que ha sido ocupado, ¿y se podría ocupar? No se sabe, puesto que ¡Necesitarías resolver el problema NP-completo!)
También te aconsejo buscar "knapsack problem", que es como se llama en inglés al problema, o "knapsack problem implementation", etc. en el web.
http://www.amazon.com/exec/obidos/ASIN/0471924202/thealgorithmrepo/103-6772389-2849416
Por tanto, he de deducir que ´buscas una solución aproximada. No tengo ni idea de si ese libro tendrá alguno (para aproximar). Creo que lo mejor que puedes hacer es un voraz con backtracking (prog. Dinámica) en la parte final, cuando el nivel de optimalidad especificado no se ha alcanzado (por ejemplo, el nivel de optimalidad sería dividir el peso obtenido con el peso total, lo que representaría el porcentaje del espacio total que ha sido ocupado, ¿y se podría ocupar? No se sabe, puesto que ¡Necesitarías resolver el problema NP-completo!)
También te aconsejo buscar "knapsack problem", que es como se llama en inglés al problema, o "knapsack problem implementation", etc. en el web.
Hola!
Si, como dices, se que es imposible resolver el problema con un NP-Completo, y lo que busco es un algoritmo alternativo que me de una solución aproximada, se que existen los algoritmos heuristicos y otras cosas, quizá uno de esos me sirva.
Muchas gracias.
Saludos
Si, como dices, se que es imposible resolver el problema con un NP-Completo, y lo que busco es un algoritmo alternativo que me de una solución aproximada, se que existen los algoritmos heuristicos y otras cosas, quizá uno de esos me sirva.
Muchas gracias.
Saludos
