Solo quería saber si existe algún algoritmo eficiente y óptimo para el problema clásico de encontrar el número mínimo de monedas que suman un número S donde S puede ser muy grande (hasta 10 ^ 16). En este caso, las monedas son (2, 5, 10). La solución DP no es lo suficientemente eficiente en este caso, por lo que me preguntaba si un enfoque ambicioso podría funcionar en este conjunto específico de monedas, pero no estoy seguro.

¡Gracias!

0
ahmedgu 18 dic. 2019 a las 21:59

2 respuestas

La mejor respuesta

Para minimizar la cantidad de monedas, notamos trivialmente que para llegar a 20, necesitamos dos 10-coins. (y no 2-coins ni 5-coins).

En términos más generales, para acercarse a 10k (con k un múltiplo de 10), solo necesitamos 10 monedas.

Ahora, para sumas que no son múltiplos de 10, es posible que queramos usar un máximo de 10 monedas. Di S = 10k + 2. El mínimo de monedas es k+1. (k 10-coins y uno 2-coin).

Entonces, el objetivo es encontrar (k,r), tal que S = 10k +r, (r < 10).

Lo hacemos trivialmente mediante el uso de% operator.

r = S % 10
k = S - S % 10

Ahora encuentre todas las combinaciones necesarias para 2-coins y 5-coins para cada r

2=2
4=2+2
5=5
6=2+2+2
7=5+2
8=2+2+2+2
9=5+2+2
1=5+2+2+2 (%10)
3=5+2+2+2+2 (%10)

Puse 1 y 3 casos en la parte inferior porque son casos especiales.

Para llegar a 21, necesitamos subir a 10, luego hacer 11 (5+2+2+2)

Lo mismo vale para 23 no podemos ir a 20, tenemos que ir a 10, luego hacer 13 (con 5+2+2+2).

El punto clave es hacer una suma con una combinación de a 2-coins y b 5-coins de modo que 2a + 5b = r % 10

Finalmente

  • para S%10=r que no esté en {1, 3}, llegue a (S - (S%10))=10k con k 10-coins y complete
  • De lo contrario, a (S - 10 - S%10)=10(k-1) con k-1 10-coins y completar

Nota final como notó @ Iłya Bursov, no podemos hacerlo para S = 1 o S = 3.

Todas las demás S pueden ser alcanzadas.

4
grodzi 18 dic. 2019 a las 19:43

Aquí hay una solución que generaliza @ grodzi, en Python. La solución depende de que las denominaciones de monedas no tengan un factor común; si lo hacen, puede ajustar la solución dividiendo todo por factor común más alto y rechazando las entradas donde esa división tiene un resto.

Para entradas suficientemente grandes, cada suma es posible. "Suficientemente grande" en este caso significa después de la primera ejecución de sumas c posibles, donde c es la denominación de moneda más grande. Podemos hacer programación dinámica para calcular soluciones hasta que se encuentre una serie de longitud c , y luego cada suma se puede resolver quitando el número apropiado de monedas de denominación c , reduciendo la suma dentro de este rango.

La complejidad temporal de la etapa de inicialización es, como máximo, O (f ( monedas ) * len ( monedas )) donde la función f proporciona Número de Frobenius del conjunto de denominaciones de monedas. La complejidad temporal del método make_change es O (len ( monedas )) más la complejidad de realizar la división entera y las operaciones con el resto, que sería O (1) en un lenguaje con límites enteros

from collections import Counter

class ChangeMaker:
    def __init__(self, *denominations):
        denominations = sorted(denominations, reverse=True)
        self.c = denominations[0]
        self.cache = [Counter()]

        def solve(n):
            for d in denominations:
                if d <= n and self.cache[n - d] is not None:
                    return Counter({ d: 1 }) + self.cache[n - d]
            return None

        run_length = 0
        while run_length < self.c:
            r = solve(len(self.cache))
            self.cache.append(r)
            if r is not None:
                run_length += 1
            else:
                run_length = 0

    def make_change(self, n):
        if n < len(self.cache):
            return self.cache[n]
        else:
            diff = n - len(self.cache) + self.c
            div = diff // self.c
            rem = diff % self.c
            cached = self.cache[len(self.cache) - self.c + rem]
            return Counter({ self.c: div }) + cached

Ejemplo:

>>> c = ChangeMaker(2, 5, 10)
>>> c.cache
[Counter(),
 None,
 Counter({2: 1}),
 None,
 Counter({2: 2}),
 Counter({5: 1}),
 Counter({2: 3}),
 Counter({5: 1, 2: 1}),
 Counter({2: 4}),
 Counter({2: 2, 5: 1}),
 Counter({10: 1}),
 Counter({2: 3, 5: 1}),
 Counter({10: 1, 2: 1}),
 Counter({2: 4, 5: 1})]
>>> c.make_change(123456789011)
Counter({10: 12345678900, 2: 3, 5: 1})
>>> c.make_change(123456789013)
Counter({10: 12345678900, 2: 4, 5: 1})
4
kaya3 18 dic. 2019 a las 20:05