🚀 go-pugleaf

El Wed, 3 Aug 2005 13:27:21 +0200, "Tomey" <kiketomey@hotmail.com>
escribi�:
>Existe algun algoritmo que dado un array tal que asi:
>14 | 36 | 45 | 8 | 45 | 55 | 55 | 55
>Haga arrays de elementos en los que que la suma de n elementos del array sea 
>lo mas proxima a 100.

�Qu� margen aceptas? Supongamos un margen absoluto (+/-)M.

A bote pronto podr�amos usar la propiedad binaria de los n�meros para
que nos generasen todas las combinaciones de n�meros. Estar�amos
limitados a 32 o 64 n�meros en el array pero es la forma m�s r�pida
que se me ocurre ahora mismo:

#include <stdin.h>
#define N 8
#define C 100.0
#define M 10.0

double matriz[N] = { 14, 36, etc};

int main () {
  unsigned int i, maximo = (2 >> N) - 1; // En este caso 255
  double suma;

  for (i = 0; i <= maximo; i++) {
    if (abs (sumar (i) - C) <= M) {
      solucion (i);
    }
  }
}

Ahora podemos definir sumar y solucion como:

double sumar (unsigned int n) {
  int i;
  double suma = 0;

  for (i = 0; i < N; i++) {
    if ((1 >> i) & n) {
      suma += matriz[i];
    }
  }
}

void solucion (unsigned int n) {
  int i;

  printf("Solucion:");
  for (i = 0; i < N; i++) {
    if ((1 >> i) & n) {
      printf(" %lf", matriz[i]);
    }
  }
  printf("\n");
}

Espero que te sirva, si necesitas este mismo algoritmo para una
longitud arbitraria de elementos d�noslo o prueba a implementar un
contador binario :)

-- 
�scar Javier Garc�a Baudet
LinaresDigital
http://redstar.linaresdigital.com/

El Wed, 3 Aug 2005 13:27:21 +0200, "Tomey" <kiketomey@hotmail.com>
escribi�:
>Serian 2n combinaciones (n = numero de elementos).

Error, el algoritmo ser�a de O(2^n) y no de O(2n). O lo que es lo
mismo, tender� a crecer exponencialmente con el n�mero de elementos.

A�n sea un algoritmo que busque la exactitud con 100 y se salte todos
aquellas combinaciones que se pasen (puede hacerse) seguir�a siendo de
orden 2^n aunque su tiempo total haya sido posiblemente reducido
sensiblemente.

Un saludo.

-- 
�scar Javier Garc�a Baudet
LinaresDigital
http://redstar.linaresdigital.com/

Si, correcto.
Se me olvido poner el ^ :P

Voy a probar el algoritmo que me has pasado a ver que tal.

Te explico exactamente el problema a ver si asi te sirve de algo mas de 
ayuda.
Una empresa me ha pedido que haga un programa que es el siguiente.

Ellos tienen barras de aluminio de 30 metros (supongamos, medida standard).
Y necesitan sacar de esas barras de aluminio 3 secciones de 10m, 5 de 43m y 
4 de 27m.
Hay que optimizar los cortes de las barras para que la perdida de material 
sea el minimo.
O si no puede ser eso, que por lo menos, el trozo de barra que te sobre sea 
reutililizable.
Que sobre un trozo de 6m no sirve para nada porque la medida menor de una 
barra es de 10m.
Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o 
superiro a 10m.

Te ha servido de algo esta explicacion????
:P
espero que si.
Bueno ahora pruebo lo que me has pasado y te cuento cosas.

Gracias.




"Oscar Garcia" <redstarQUITARSPAM23@terra.es> escribi� en el mensaje 
news:7vl1f11q6kjm53bfqdhid70hfvti4pfimm@4ax.com...
> El Wed, 3 Aug 2005 13:27:21 +0200, "Tomey" <kiketomey@hotmail.com>
> escribi�:
>>Serian 2n combinaciones (n = numero de elementos).
>
> Error, el algoritmo ser�a de O(2^n) y no de O(2n). O lo que es lo
> mismo, tender� a crecer exponencialmente con el n�mero de elementos.
>
> A�n sea un algoritmo que busque la exactitud con 100 y se salte todos
> aquellas combinaciones que se pasen (puede hacerse) seguir�a siendo de
> orden 2^n aunque su tiempo total haya sido posiblemente reducido
> sensiblemente.
>
> Un saludo.
>
> -- 
> �scar Javier Garc�a Baudet
> LinaresDigital
> http://redstar.linaresdigital.com/ 

Rectifico.
donde he dicho
"Ellos tienen barras de aluminio de 30 metros (supongamos, medida 
standard)."
queria decir
"Ellos tienen barras de aluminio de 60 metros (supongamos, medida 
standard)."

�Todas estas medidas son exagerando un poco.!


"Tomey" <kiketomey@hotmail.com> escribi� en el mensaje 
news:dcqon1$p3r$1@nsnmrro2-gest.nuria.telefonica-data.net...
> Si, correcto.
> Se me olvido poner el ^ :P
>
> Voy a probar el algoritmo que me has pasado a ver que tal.
>
> Te explico exactamente el problema a ver si asi te sirve de algo mas de 
> ayuda.
> Una empresa me ha pedido que haga un programa que es el siguiente.
>
> Ellos tienen barras de aluminio de 30 metros (supongamos, medida 
> standard).
> Y necesitan sacar de esas barras de aluminio 3 secciones de 10m, 5 de 43m 
> y 4 de 27m.
> Hay que optimizar los cortes de las barras para que la perdida de material 
> sea el minimo.
> O si no puede ser eso, que por lo menos, el trozo de barra que te sobre 
> sea reutililizable.
> Que sobre un trozo de 6m no sirve para nada porque la medida menor de una 
> barra es de 10m.
> Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o 
> superiro a 10m.
>
> Te ha servido de algo esta explicacion????
> :P
> espero que si.
> Bueno ahora pruebo lo que me has pasado y te cuento cosas.
>
> Gracias.
>
>
>
>
> "Oscar Garcia" <redstarQUITARSPAM23@terra.es> escribi� en el mensaje 
> news:7vl1f11q6kjm53bfqdhid70hfvti4pfimm@4ax.com...
>> El Wed, 3 Aug 2005 13:27:21 +0200, "Tomey" <kiketomey@hotmail.com>
>> escribi�:
>>>Serian 2n combinaciones (n = numero de elementos).
>>
>> Error, el algoritmo ser�a de O(2^n) y no de O(2n). O lo que es lo
>> mismo, tender� a crecer exponencialmente con el n�mero de elementos.
>>
>> A�n sea un algoritmo que busque la exactitud con 100 y se salte todos
>> aquellas combinaciones que se pasen (puede hacerse) seguir�a siendo de
>> orden 2^n aunque su tiempo total haya sido posiblemente reducido
>> sensiblemente.
>>
>> Un saludo.
>>
>> -- 
>> �scar Javier Garc�a Baudet
>> LinaresDigital
>> http://redstar.linaresdigital.com/
>
> 

Hola, Tomey:

Tomey escribi� en es.comp.os.linux.programacion:

> Si, correcto.
> Se me olvido poner el ^ :P
> 
> Voy a probar el algoritmo que me has pasado a ver que tal.
> 
> Te explico exactamente el problema a ver si asi te sirve de algo mas de
> ayuda.
> Una empresa me ha pedido que haga un programa que es el siguiente.
> 
> Ellos tienen barras de aluminio de 30 metros (supongamos, medida
> standard). Y necesitan sacar de esas barras de aluminio 3 secciones de
> 10m, 5 de 43m y 4 de 27m.
> Hay que optimizar los cortes de las barras para que la perdida de material
> sea el minimo.
> O si no puede ser eso, que por lo menos, el trozo de barra que te sobre
> sea reutililizable.

�De cu�ntas barras estamos hablando?

En principio, el problema parece NP-Dif�cil (t=>a^n), no obstante, con un
n�mero relativamente bajo de barras, y si el tiempo no es cr�tico, puedes
optar por la cosa m�s sencilla: hacer una b�squeda exhaustiva en el espacio
de soluciones (es decir, calcular *todas* las soluciones posibles y
quedarte con la mejor).  Es problable que si el stock es menor que,
digamos, 100 barras, eso te sea suficiente si puedes obtener la soluci�n
en, digamos, menos de una o dos horas (el hecho de que una soluci�n sea
"fea" en t�rminos absolutos, no quiere decir que no pueda ser perfectamente
viable en tu entorno real).

Si ves que el proceso es demasiado largo para tus necesidades, puedes
utilizar el m�todo de bipartici�n, que deber�a ser lineal: simplemente coge
la secci�n m�s larga, y luego la m�s larga que te quede (y que entre en el
resto), de entre las restantes, sucesivamente hasta que no te quepa ninguna
m�s.  No voy a echar n�meros ahora, pero tiene pinta de ser una
aproximaci�n "suficientemente buena".  La suposici�n que hago es que todas
las barras que utilizas son del mismo tama�o, ya que no dices otra cosa.

> Que sobre un trozo de 6m no sirve para nada porque la medida menor de una
> barra es de 10m.
> Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o
> superiro a 10m.

Con esta constricci�n, juega con dos barras, una "real" y otra "virtual"
diez metros m�s corta; si consigues que a la barra "virtual" le sobre menos
material que a la barra "real", �sa es tu soluci�n; en caso contrario, usa
la soluci�n obtenida para la barra "real".

Veamos un ejemplo pr�ctico con los datos que das:

Primera barra:
        27m (nos sobran tres metros, que es un tama�o mayor que la secci�n m�s
peque�a, por lo que ya no podemos seguir; veamos que pasa con la barra
"virtual" de 20m):
                10m+10m (no sobra nada, por lo tanto cogemos esta soluci�n y nos queda un
"resto" de 10m, que volvemos a partir):
                10m (no sobra nada, y ya hemos acabado con las secciones de 10m)
Segunda barra:
        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" de 20m;
voy a suponer que donde dices 5 secciones de 43m son 10 secciones de 5m, ya
que las de 43m no "caben" en la barra de 30m, y con 43 barras, el ejemplo
sale demasiado largo):
                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta soluci�n y nos queda
un "resto" de 10m, que volvemos a partir):
                5m+5m (no sobra nada)
Tercera barra:
        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" de
20m):
                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta soluci�n y ya no nos
quedan secciones de cinco metros; nos queda un "resto" de 10m, que
intentamos volver a partir, pero no podemos, porque no nos quedan ya
perfiles iguales o menores que 10m para encajar).
Cuarta, quinta, sexta y s�ptima barras: 27m, y nos sobran tres pedazos de 3m
de cada una (la soluci�n de la "barra virtual" la omito porque es evidente
que no va a ser mejor).

Ya hemos acabado.  En este caso, adem�s, se puede demostrar que hemos
encontrado la soluci�n �ptima*1: el reparto no pod�a hacerse de mejor
manera, porque la secci�n m�s larga (la de 27m) no dejaba sitio en la barra
para la secci�n m�s peque�a (la de 10m) 

Pueden existir optimizaciones locales "parientes" de los algoritmos de
ordenaci�n, pero no las busques a menos que realmente las necesites (ya
sabes, "early optimization is the root of all evils"): por ejemplo, puesto
que hemos ordenado las secciones de mayor a menor, una vez que la barra m�s
corta que nos queda no quepa en la "barra virtual", sabemos que ya no nos
hace falta intentar con ella en iteraciones posteriores; o, si en la barra
entran muchas secciones, o si tenemos muchos tama�os distintos a encajar,
podemos avanzar "a saltos" 2:1 o 3:1 para encontrar la secci�n adecuada
cuando las mayores ya no nos quepan, o puedes probar a colocar los perfiles
en lugar de mayor a menor, de forma alterna mayor-menor-mayor-menor...

*1 En general, puedes calcular heur�sticamente si esta aproximaci�n es
razonablemente buena utilizando un m�todo de montecarlo para generar
pedidos aleatorios (la generaci�n de pedidos la puedes sustituir, por
ejemplo, por el listado de pedidos del �ltimo a�o, si tienes acceso a �l),
y luego calculando el resto �ptimo si s�lo tuvieras una barra de longitud
m�ltiplo de la barra real, compar�ndolo con el que te da el procedimiento
que te he contado.
En el ejemplo: 3*10 + 10*5 + 4*27 = 188m
               7*30=210m
               210-188=22m sobrantes
As�, sabemos que en la soluci�n ideal nos van a sobrar por lo menos 22m
(justo lo que nos sobr� a nosotros, por eso sabemos que nuestra soluci�n
era ideal).  Puesto que no tenemos una barra de 210m, sino muchas de 30,
podr�a darse el caso de la soluci�n �ptima te�rica no existiese: por
ejemplo, supongamos que nos piden 12 perfiles de 25m; el �ptimo te�rico
ser�a (12*25=300; 300/30=10) utilizar diez barras sin que nos sobrase nada,
pero es obvio que en este caso necesitar�amos 12 barras y nos sobrar�an 12
trozos de cinco metros.  As�, aunque no sabemos realmente cu�n cerca
estamos del �ptimo real (para ello habr�a que calcular exhaustivamente los
�ptimos reales y compararlos con las soluciones obtenidas, o poder
demostrar matem�ticamente la aproximaci�n del algoritmo en el paso al
l�mite -existe toda una rama de la matem�tica que se dedica a estas cosas-)
s� tenemos una idea aproximada de lo bien que lo estamos haciendo.  Si,
adem�s, tienes acceso a los pedidos del �ltimo a�o, puedes establecer si el
m�todo es mejor que el que ten�a la empresa, tanto calcul�sticamente
(cu�ntas barras utilizaron realmente y cu�ntas hubieran utilizado caso de
usar tu programa), como en tiempo (cu�nto tiempo les llev� hacer los
c�lculos -si esa informaci�n existe- y cu�nto les hubiera costado de haber
utilizado tu programa).  Puede darse el caso de que incluso si tu programa
fuese peor que el m�todo que estuviesen utilizando hasta ahora, fuese
rentable si, por ejemplo, se pasase de usar dos horas diarias de operador
con l�piz y papel, a utilizar 10 minutos diarios de tiempo de ordenador. 
Si la diferencia es sustancial, incluso puedes plantear un aumento de
sueldo por una fracci�n del dinero que les est�s ahorrando.
-- 
SALUD,
Jes�

Hola Jesus.

Me acaban de pasar un caso real de pedido.
Te cuento:

Una barra mide 6400 mm.

Y en el pedidon piden:

+ 80 de 648,4 mm
+ 100 de 768,4 mm
+ 100 de 708,4 mm

De ahi hay que sacar cuantas barras se van a necesitar y la combinaci�n de 
los cortes para que el desperdicio sea el menor posible. Un desperdicio 
optimo para la empresa son 30 mm o menos por barra. O si no que me sobre 
entre 768,4 mm y 1248,4 mm (480mm).

Lo optimo serian usar :
80 * 348,4 + 100 * 768,4 + 100 *  708,4 = 175552 mm
28 * 6400 = 179200 mm
179200 - 175552 = 3648 mm = 3,648 m

Y a ver, si he entendido bien tu planteamiento.

Si corto la barra REAL (6400mm) con una combinacion de cortes X y nos sobran 
menos de 30mm, entonces perfecto esa combinacion es correcta.
Ahora, si nos sobran m�s de 30mm, entonces paso a la barra VIRTUAL de 5920 
mm (6400mm - 480 mm) y si en esta barra nos sobran menos de 30mm entonces 
esta es la mejor opcion. Y si nos sobran m�s de 30 mm entonces elijo la 
barra REAL.

�Es correcto?
O viendo el pedido que te he puesto arriba, �como lo solucionarias?, �de la 
misma forma que me has dicho?.

Muchas Gracias, Jesus.




"Jes�s M. NAVARRO" <jmnavarrol@able.es> escribi� en el mensaje 
news:qph7s2-asj.ln1@mithrandir.intranet...
> Hola, Tomey:
>
> Tomey escribi� en es.comp.os.linux.programacion:
>
>> Si, correcto.
>> Se me olvido poner el ^ :P
>>
>> Voy a probar el algoritmo que me has pasado a ver que tal.
>>
>> Te explico exactamente el problema a ver si asi te sirve de algo mas de
>> ayuda.
>> Una empresa me ha pedido que haga un programa que es el siguiente.
>>
>> Ellos tienen barras de aluminio de 30 metros (supongamos, medida
>> standard). Y necesitan sacar de esas barras de aluminio 3 secciones de
>> 10m, 5 de 43m y 4 de 27m.
>> Hay que optimizar los cortes de las barras para que la perdida de 
>> material
>> sea el minimo.
>> O si no puede ser eso, que por lo menos, el trozo de barra que te sobre
>> sea reutililizable.
>
> �De cu�ntas barras estamos hablando?
>
> En principio, el problema parece NP-Dif�cil (t=>a^n), no obstante, con un
> n�mero relativamente bajo de barras, y si el tiempo no es cr�tico, puedes
> optar por la cosa m�s sencilla: hacer una b�squeda exhaustiva en el 
> espacio
> de soluciones (es decir, calcular *todas* las soluciones posibles y
> quedarte con la mejor).  Es problable que si el stock es menor que,
> digamos, 100 barras, eso te sea suficiente si puedes obtener la soluci�n
> en, digamos, menos de una o dos horas (el hecho de que una soluci�n sea
> "fea" en t�rminos absolutos, no quiere decir que no pueda ser 
> perfectamente
> viable en tu entorno real).
>
> Si ves que el proceso es demasiado largo para tus necesidades, puedes
> utilizar el m�todo de bipartici�n, que deber�a ser lineal: simplemente 
> coge
> la secci�n m�s larga, y luego la m�s larga que te quede (y que entre en el
> resto), de entre las restantes, sucesivamente hasta que no te quepa 
> ninguna
> m�s.  No voy a echar n�meros ahora, pero tiene pinta de ser una
> aproximaci�n "suficientemente buena".  La suposici�n que hago es que todas
> las barras que utilizas son del mismo tama�o, ya que no dices otra cosa.
>
>> Que sobre un trozo de 6m no sirve para nada porque la medida menor de una
>> barra es de 10m.
>> Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o
>> superiro a 10m.
>
> Con esta constricci�n, juega con dos barras, una "real" y otra "virtual"
> diez metros m�s corta; si consigues que a la barra "virtual" le sobre 
> menos
> material que a la barra "real", �sa es tu soluci�n; en caso contrario, usa
> la soluci�n obtenida para la barra "real".
>
> Veamos un ejemplo pr�ctico con los datos que das:
>
> Primera barra:
>        27m (nos sobran tres metros, que es un tama�o mayor que la secci�n 
> m�s
> peque�a, por lo que ya no podemos seguir; veamos que pasa con la barra
> "virtual" de 20m):
>                10m+10m (no sobra nada, por lo tanto cogemos esta soluci�n 
> y nos queda un
> "resto" de 10m, que volvemos a partir):
>                10m (no sobra nada, y ya hemos acabado con las secciones de 
> 10m)
> Segunda barra:
>        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" 
> de 20m;
> voy a suponer que donde dices 5 secciones de 43m son 10 secciones de 5m, 
> ya
> que las de 43m no "caben" en la barra de 30m, y con 43 barras, el ejemplo
> sale demasiado largo):
>                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta 
> soluci�n y nos queda
> un "resto" de 10m, que volvemos a partir):
>                5m+5m (no sobra nada)
> Tercera barra:
>        27m (nos sobran tres metros; veamos que pasa con la barra "virtual" 
> de
> 20m):
>                5m+5m+5m+5m (no sobra nada, por lo tanto cogemos esta 
> soluci�n y ya no nos
> quedan secciones de cinco metros; nos queda un "resto" de 10m, que
> intentamos volver a partir, pero no podemos, porque no nos quedan ya
> perfiles iguales o menores que 10m para encajar).
> Cuarta, quinta, sexta y s�ptima barras: 27m, y nos sobran tres pedazos de 
> 3m
> de cada una (la soluci�n de la "barra virtual" la omito porque es evidente
> que no va a ser mejor).
>
> Ya hemos acabado.  En este caso, adem�s, se puede demostrar que hemos
> encontrado la soluci�n �ptima*1: el reparto no pod�a hacerse de mejor
> manera, porque la secci�n m�s larga (la de 27m) no dejaba sitio en la 
> barra
> para la secci�n m�s peque�a (la de 10m)
>
> Pueden existir optimizaciones locales "parientes" de los algoritmos de
> ordenaci�n, pero no las busques a menos que realmente las necesites (ya
> sabes, "early optimization is the root of all evils"): por ejemplo, puesto
> que hemos ordenado las secciones de mayor a menor, una vez que la barra 
> m�s
> corta que nos queda no quepa en la "barra virtual", sabemos que ya no nos
> hace falta intentar con ella en iteraciones posteriores; o, si en la barra
> entran muchas secciones, o si tenemos muchos tama�os distintos a encajar,
> podemos avanzar "a saltos" 2:1 o 3:1 para encontrar la secci�n adecuada
> cuando las mayores ya no nos quepan, o puedes probar a colocar los 
> perfiles
> en lugar de mayor a menor, de forma alterna mayor-menor-mayor-menor...
>
> *1 En general, puedes calcular heur�sticamente si esta aproximaci�n es
> razonablemente buena utilizando un m�todo de montecarlo para generar
> pedidos aleatorios (la generaci�n de pedidos la puedes sustituir, por
> ejemplo, por el listado de pedidos del �ltimo a�o, si tienes acceso a �l),
> y luego calculando el resto �ptimo si s�lo tuvieras una barra de longitud
> m�ltiplo de la barra real, compar�ndolo con el que te da el procedimiento
> que te he contado.
> En el ejemplo: 3*10 + 10*5 + 4*27 = 188m
>               7*30=210m
>               210-188=22m sobrantes
> As�, sabemos que en la soluci�n ideal nos van a sobrar por lo menos 22m
> (justo lo que nos sobr� a nosotros, por eso sabemos que nuestra soluci�n
> era ideal).  Puesto que no tenemos una barra de 210m, sino muchas de 30,
> podr�a darse el caso de la soluci�n �ptima te�rica no existiese: por
> ejemplo, supongamos que nos piden 12 perfiles de 25m; el �ptimo te�rico
> ser�a (12*25=300; 300/30=10) utilizar diez barras sin que nos sobrase 
> nada,
> pero es obvio que en este caso necesitar�amos 12 barras y nos sobrar�an 12
> trozos de cinco metros.  As�, aunque no sabemos realmente cu�n cerca
> estamos del �ptimo real (para ello habr�a que calcular exhaustivamente los
> �ptimos reales y compararlos con las soluciones obtenidas, o poder
> demostrar matem�ticamente la aproximaci�n del algoritmo en el paso al
> l�mite -existe toda una rama de la matem�tica que se dedica a estas 
> cosas-)
> s� tenemos una idea aproximada de lo bien que lo estamos haciendo.  Si,
> adem�s, tienes acceso a los pedidos del �ltimo a�o, puedes establecer si 
> el
> m�todo es mejor que el que ten�a la empresa, tanto calcul�sticamente
> (cu�ntas barras utilizaron realmente y cu�ntas hubieran utilizado caso de
> usar tu programa), como en tiempo (cu�nto tiempo les llev� hacer los
> c�lculos -si esa informaci�n existe- y cu�nto les hubiera costado de haber
> utilizado tu programa).  Puede darse el caso de que incluso si tu programa
> fuese peor que el m�todo que estuviesen utilizando hasta ahora, fuese
> rentable si, por ejemplo, se pasase de usar dos horas diarias de operador
> con l�piz y papel, a utilizar 10 minutos diarios de tiempo de ordenador.
> Si la diferencia es sustancial, incluso puedes plantear un aumento de
> sueldo por una fracci�n del dinero que les est�s ahorrando.
> -- 
> SALUD,
> Jes�s 

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--8323328-1179225421-1123185831=:19063
Content-Type: TEXT/PLAIN; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Thu, 4 Aug 2005, Tomey wrote:

> Hola Jesus.
>
> Me acaban de pasar un caso real de pedido.
> Te cuento:
>
> Una barra mide 6400 mm.
>
> Y en el pedidon piden:
>
> + 80 de 648,4 mm
> + 100 de 768,4 mm
> + 100 de 708,4 mm

Bueno, como es un pedido r=E1pido ah=ED va una respuesta r=E1pida

Estas son las combinaciones =F3ptimas:

A B C    LONGITUD=20
0 0 9 -> 6375.6
1 1 7 -> 6375.6
3 3 3 -> 6375.6

A eso no se le puede mejorar. Luego tomamos

3 A 3 B 3 C -> 78, 26 veces
1 A 1 B 7 C -> 2 A y B, 14C
quedan 0 A 20 B 8 C
=2E..

luego ya hemos simplificado el problema a cortar s=F3lo
20 B y 8 C de la mejor forma posible.
Saludos,

--8323328-1179225421-1123185831=:19063--

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Tomey escribi�:
> Te explico exactamente el problema a ver si asi te sirve de algo mas de 
> ayuda.
> Una empresa me ha pedido que haga un programa que es el siguiente.
>
> Ellos tienen barras de aluminio de 30 metros (supongamos, medida standard).
> Y necesitan sacar de esas barras de aluminio 3 secciones de 10m, 5 de 43m y 
> 4 de 27m.
> Hay que optimizar los cortes de las barras para que la perdida de material 
> sea el minimo.
> O si no puede ser eso, que por lo menos, el trozo de barra que te sobre sea 
> reutililizable.
> Que sobre un trozo de 6m no sirve para nada porque la medida menor de una 
> barra es de 10m.
> Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o 
> superiro a 10m.
>

Ese problema descrito es bastante conocido bajo el nombre del �problema
de la mochila�. El planteamiento es que tienes que meter en la mochila
objetos de diferente tama�o para que el espacio desaprovechado sea
m�nimo. 

Es un problema complejo y est� bastante documentado en muchos sitios.
Concretamente, hace alg�n tiempo, publiqu� en Libertonia un par de
art�culos referidos a este problema con software que calcula lo que
pides. 

El resumen y enlaces (con alguna actualizaci�n) est� en :
http://barbacana.net/drupal/node/239

el problema que me planteaba en aqu�l caso es: como repartir directorios
de canciones en CDROMS. Realmente, al programa le daba igual las
unidades que uses, donde dice capacidad pones la longitud de la barra
original y en los directorios las barras que necesitas obtener y ya te
hace la optimizaci�n adecuada.

Ah, el algoritmo que emplea es una b�squeda usando algoritmos gen�ticos
y est� implementado en Perl.

atte. javier m mora

- -- 
	Javier Maria Mora Merchan
	(GPGP) Key ID: 0x794F3D83

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFC8ozqpRHCj3lPPYMRAhGzAKCwKWvw66pBKUcKk+XCebN0psaEgQCdH8LY
CsA8xGEGv6YVDAt02OokGdc=
=x3tk
-----END PGP SIGNATURE-----

He estado mirando en codigo de Perl, pero no me aclaro mucho la verdad. :P
He encontrado bastante informacion sobre el problema.
Se le llama de varias formas "cutting stock problem" o "knapsack problem". 
Lo que no he conseguido encontrar en una implementacion del problema en C++.

�Alguien lo tiene implementado?



"Javier M Mora (jamarier)" <javiermm@bigNOfootSPAM.com> escribi� en el 
mensaje news:dcu2bg$i3q$1@appleseed.escomposlinux.org...
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Tomey escribi�:
>> Te explico exactamente el problema a ver si asi te sirve de algo mas de
>> ayuda.
>> Una empresa me ha pedido que haga un programa que es el siguiente.
>>
>> Ellos tienen barras de aluminio de 30 metros (supongamos, medida 
>> standard).
>> Y necesitan sacar de esas barras de aluminio 3 secciones de 10m, 5 de 43m 
>> y
>> 4 de 27m.
>> Hay que optimizar los cortes de las barras para que la perdida de 
>> material
>> sea el minimo.
>> O si no puede ser eso, que por lo menos, el trozo de barra que te sobre 
>> sea
>> reutililizable.
>> Que sobre un trozo de 6m no sirve para nada porque la medida menor de una
>> barra es de 10m.
>> Entonces digamos que el sobrante debe estar lo mas cercanoa a 0 posible o
>> superiro a 10m.
>>
>
> Ese problema descrito es bastante conocido bajo el nombre del �problema
> de la mochila�. El planteamiento es que tienes que meter en la mochila
> objetos de diferente tama�o para que el espacio desaprovechado sea
> m�nimo.
>
> Es un problema complejo y est� bastante documentado en muchos sitios.
> Concretamente, hace alg�n tiempo, publiqu� en Libertonia un par de
> art�culos referidos a este problema con software que calcula lo que
> pides.
>
> El resumen y enlaces (con alguna actualizaci�n) est� en :
> http://barbacana.net/drupal/node/239
>
> el problema que me planteaba en aqu�l caso es: como repartir directorios
> de canciones en CDROMS. Realmente, al programa le daba igual las
> unidades que uses, donde dice capacidad pones la longitud de la barra
> original y en los directorios las barras que necesitas obtener y ya te
> hace la optimizaci�n adecuada.
>
> Ah, el algoritmo que emplea es una b�squeda usando algoritmos gen�ticos
> y est� implementado en Perl.
>
> atte. javier m mora
>
> - -- 
> Javier Maria Mora Merchan
> (GPGP) Key ID: 0x794F3D83
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
>
> iD8DBQFC8ozqpRHCj3lPPYMRAhGzAKCwKWvw66pBKUcKk+XCebN0psaEgQCdH8LY
> CsA8xGEGv6YVDAt02OokGdc=
> =x3tk
> -----END PGP SIGNATURE----- 

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

--8323328-1595586014-1123241059=:27392
Content-Type: TEXT/PLAIN; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: QUOTED-PRINTABLE

On Fri, 5 Aug 2005, Tomey wrote:

> He estado mirando en codigo de Perl, pero no me aclaro mucho la verdad. :=
P
> He encontrado bastante informacion sobre el problema.
> Se le llama de varias formas "cutting stock problem" o "knapsack problem"=
=2E
> Lo que no he conseguido encontrar en una implementacion del problema en C=
++.
>
> =BFAlguien lo tiene implementado?
>
No, lo que t=FA necesitas es una librer=EDa o c=F3digo de BinPacking 1D
Por ejemplo, en Perl Algorithm-BinPack*gz (search.cpan.org)

La diferencia radica en que t=FA tienes N mochilas, y quieres minimizar N,
lo cual es similar pero no equivalente al knapsack.
Saludos,

--8323328-1595586014-1123241059=:27392--