Algoritmos codiciosos para sumas

 

Este tipo de algoritmo recibe muchos nombres distintos: voraz, goloso, devorador, codicioso, greedy,…Se basa en la estrategia de elegir en cada paso la solución óptima del problema, esperando que, al reiterar esta estrategia, se construya una solución óptima global. Para conseguirlo, no da marcha atrás en las decisiones si no se llega a un óptimo. Esto lo hace más rápido, pero más inseguro, porque no hay garantía de consecución de objetivos.

Ha de ser posible la elección óptima en cada paso, como en el caso de descomposición en suma de factoriales, que siempre se puede conocer el mayor factorial menor o igual que el número dado

Aquí estudiaremos varios ejemplos de descomposición de un número entero positivo en sumandos de un cierto tipo. Un ejemplo claro es el de encontrar una suma de factoriales cuyo resultado sea un número dado. Este algoritmo lo llevamos usando años en nuestras publicaciones, porque es rápido, aunque en ocasiones produce soluciones con un número alto de sumandos.

Lo vemos con un ejemplo elegido al azar, el número 1329, al que queremos convertir en una suma de factoriales lo menos extensa posible.

Es claro que si no deseamos muchos sumandos, vayamos eligiendo los factoriales mayores posibles para construir la suma. Podríamos efectuarlo así:

1329-720=609
609-120=489
489-120=369
369-120=249
249-120=129
129-120=9
9-6=3
3-2=1
1-1=0

Con ello, hemos descompuesto 1329 en suma de factoriales:

1329=720+120+120+120+120+120+6+2+1

Basta analizar la solución para darnos cuenta de que no podemos esperar demasiado de este algoritmo, pero al contar con el 1 entre los factoriales, siempre dará solución.

Un caso similar es el de descomponer una fracción en fracciones egipcias (del tipo 1/p). Bastará ir buscando en el numerador el mayor divisor posible del denominador (suponemos fracción irreducible). Por ejemplo, la fracción 17/24 se puede descomponer de esta forma, eligiendo en el numerador sucesivamente los mayores divisores de 24:

17/24=(12+4+1)/24=1/2+1/6+1/24

Los dos ejemplos los hemos desarrollado de forma manual, pero es claro que se podrá automatizar fácilmente.

Para planificar los algoritmos, distinguiremos dos variantes:

La primera requerirá que los sumandos pertenezcan a un mismo tipo, como los factoriales de más arriba, o, por ejemplo el problema de descomponer un número en sumandos triangulares.

La segunda, muy parecida a la primera, deberá elegir los sumandos dentro de una lista, como en el problema de las monedas, en el que una cantidad hay que traducirla a un conjunto de monedas con distintos valores.

En realidad, el ejemplo de los factoriales se puede considerar de este segundo tipo, por su escasez.

Sumandos del mismo tipo

Si el sumando óptimo lo debemos elegir dentro de un tipo, como primos, cuadrados o pentagonales, podremos usar un sencillo algoritmo que el autor usa con frecuencia. Tendría esta estructura, en la que, para un número n y un tipo dado, devuelve la suma más adecuada que un algoritmo codicioso puede dar.

Function codicioso$(n)
Dim c$
Dim i, r, s,suma
Dim vale As Boolean

suma = 0 'Irá sumando progresivamente
i = n ‘Recorrerá los posibles sumandos
r = n ‘Posible sumando válido
c = "" ’Recogerá soluciones
While i > 0 ‘Recorremos de mayor a menor, para optimizar
vale = False ‘Aún no hay solución
if CONDICION then vale=true ‘La CONDICIÓN dependerá del tipo de sumandos
If vale Then
c$ = c$ + Str$(i) + "  "
suma=suma+i
‘Si existe solución, se resta y se incorpora a la suma
r = r - i: i = r
Else
‘Si no existe solución, se sigue buscando el óptimo, descendiendo
i = i – 1
end if
Wend
If suma=n then codicioso = c else codicioso=”NO”
End Function

Por ejemplo, si la condición es la de ser primo, usaríamos la función ESPRIMO, fácilmente localizable en nuestro blog. En la tabla siguiente se recogen las sumas en números primos, si es que son posibles, para los primeros números de tres cifras:

Este ejemplo es muy interesante, porque ilustra las limitaciones de los algoritmos codiciosos. En primer lugar, sólo figuran los números en los que, al finalizar el algoritmo, la suma coincide con ellos, sin dejar ningún residuo no primo. Por ejemplo, el 15 daría como resultado 7+7, y sobraría 1, porque no es primo. En segundo lugar, al no explorar todas las posibilidades, ignora las sumas de Golbach para números pares, porque se detiene antes de llegar a los dos primos que predice la conjetura. Por ejemplo, el número 104, que no figura en la tabla, presenta varias descomposiciones en sumas de dos primos, y el algoritmo codicioso las ignora:

No obstante, en sumados de algunos tipos, el algoritmo funciona relativamente bien. Por ejemplo, cuando el 1 pertenece a ese tipo, como ocurriría en los cuadrados, triangulares, palindrómicos o de Fibonacci, la descomposición siempre será exitosa, aunque, quizás, algo larga. También suele funcionar bien con primos y cuadrados de primos, y con oblongos si el número es par. El siguiente ejemplo contiene resultados de cuadrados de primos entre 375 y 400:

En este caso están condicionados por el cuadrado de 19, 361. En general suelen aparecer los ejemplos con una cierta rapidez.

Un ejemplo clásico, y que publicamos a veces, es el de la representación de Zeckendorf, en la que todo número es suma de elementos de la sucesión de Fibonacci (ver, por ejemplo, nuestra entrada

https://hojaynumeros.blogspot.com/2020/09/representacion-de-zeckendorf.html).

En ella el algoritmo indicado es el codicioso. Hemos aplicado la función que presentamos más arriba a un conjunto de números consecutivos, y observamos que todos están representados así:

Puedes decubrir aspectos muy interesantes sobre esta descomposición en

https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem

Sumandos dentro de una lista

Este otro tipo de descomposición en sumandos que se adapta bien a los algoritmos codiciosos, es el de expresar un número como suma de números ya fijados en una lista. De este tipo es el problema de las monedas, en el que hay que encontrar la forma de pagar una cantidad si se dispone de un número suficiente de monedas de varias clases.

En este blog hemos tratado este tema y otros similares, como el de los números McNugget y la representación de un número respecto a una lista:

https://hojaynumeros.blogspot.com/2010/02/frobenius-y-los-mcnuggets.html

https://hojaynumeros.blogspot.com/2012/11/descomposicion-de-un-numero-segun-una.html

Por ejemplo, si nos piden representar el número 80 mediante los números de la lista 2, 4, 14, 32, procederíamos como en los problemas anteriores, restando de 80 el número mayor posible cada vez, y usando repeticiones:

48=80-32; 16=38-32; 16=14+2

Luego 80=32+32+14+2

No hemos necesitado el sumando 4.

El procedimiento usado para sumandos del mismo tipo es válido aquí, pero deberemos iniciar el algoritmo declarando los elementos de la lista según un vector.

Algo similar usa las herramientas que ofrecemos en hojamat.es:

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum

http://www.hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#mcnugget

Aquí seguiremos usando una función como en el primer caso, pero declarando los sumandos. Los introduciremos como componentes de un vector. Por ejemplo, en el siguiente listado se pretende encontrar qué monedas y billetes de euro podemos usar en una compra ordinaria, sin céntimos, y con un tope del billete de 50€:

Function codicioso3$(n)
Dim c$
Dim i, j, r, s, suma, tope
Dim v(20) ‘Usamos un vector de 20 componentes
v(1) = 1: v(2) = 2: v(3) = 5: v(4) = 10: v(5) = 20: v(6) = 50
tope = 6 ‘Determinamos seis monedas y billetes

‘El resto del listado es muy similar al del anterior tipo

suma = 0 'Irá sumando progresivamente
i = n 'Recorrerá los posibles sumandos
r = n 'Posible sumando válido
c = "" 'Recogerá soluciones
j = tope
While i > 0 And j > 0 'Recorremos de mayor a menor, para optimizar
If i >= v(j) Then
c$ = c$ + Str$(v(j)) + "  "’Aquí sumamos componentes del vector
suma = suma + v(j)
i = i - v(j)
Else

'Si no existe solución, se sigue buscando el óptimo, descendiendo

j = j - 1
End If
Wend
If suma = n Then codicioso3 = c Else codicioso3 = "NO"
End Function

Como ejemplo, insertamos una tabla con algunas cantidades en euros y su descomposición en monedas y billetes:

Hay que volver a advertir que estas soluciones no han de ser ni únicas ni óptimas.