algorithm - programacion - ¿Por qué el algoritmo de cambio de moneda codiciosa no funciona para algunos juegos de monedas?
programacion dinamica ejemplos sencillos (5)
En cualquier caso donde no hay una moneda cuyo valor, cuando se agrega a la denominación más baja, es menor que el doble de la denominación inmediatamente inferior, el algoritmo codicioso funciona.
es decir, {1,2,3} funciona porque [1,3] y [2,2] se suman al mismo valor; sin embargo, {1, 15, 25} no funciona porque (para el cambio 30) 15 + 15> 25 +1
Entiendo cómo funciona el algoritmo codicioso para el problema de cambio de moneda (pagar una cantidad específica con la cantidad mínima posible de monedas) - siempre selecciona la moneda con la denominación más grande que no exceda la suma restante - y que siempre encuentra la solución correcta para conjuntos de monedas específicos.
Pero para algunos juegos de monedas, hay sumas para las cuales el algoritmo codicioso falla. Por ejemplo, para el conjunto {1, 15, 25} y la suma 30, el algoritmo codicioso primero elige 25, dejando un resto de 5 y luego cinco 1 para un total de seis monedas. Pero la solución con el número mínimo de monedas es elegir 15 dos veces.
¿Qué condiciones debe cumplir un conjunto de monedas para que el algoritmo codicioso encuentre la solución mínima para todas las sumas?
Este es un problema de recurrencia. Dado un conjunto de monedas {Cn, Cn-1, . . ., 1} {Cn, Cn-1, . . ., 1} {Cn, Cn-1, . . ., 1} , de modo que para 1 <= k <= n, Ck > Ck-1 , el algoritmo codicioso dará el número mínimo de monedas si Ck> Ck-1 + Ck-2 y para el valor V=(Ck + Ck-1) - 1 , aplicando el algoritmo codicioso al subconjunto de monedas {Ck, Ck-1, . . ., 1} {Ck, Ck-1, . . ., 1} {Ck, Ck-1, . . ., 1} , donde Ck <= V , resulta en menos monedas que el número resultante de la aplicación del algoritmo codicioso al subconjunto de monedas {Ck-1, Ck-2, . . ., 1} {Ck-1, Ck-2, . . ., 1} {Ck-1, Ck-2, . . ., 1} .
La prueba es simple: para `1 <= k <= n pruebe el número de monedas que el algoritmo de Greedy arroja para un valor de Ck + Ck-1 - 1. Haga esto para el conjunto de monedas {Ck, Ck-1,. . ., 1} y {Ck-1, Ck-2,. . ., 1}. Si para cualquier k, este último produce menos monedas que el primero, el algoritmo de Greedy no funcionará para este conjunto de monedas.
Por ejemplo, con n = 4, considere el conjunto de monedas {C4, C3, C2, 1} = {50,25,10,1}. Comience con k = n = 4, luego V = Cn + Cn-1 - 1 = 50 + 25-1 = 74 como valor de prueba. Para V = 74, G {50,25,10,1} = 7 monedas. G {25, 10, 1} = 8 monedas. Hasta aquí todo bien. Ahora deja k = 3. luego V = 25 + 10-1 = 34. G {25, 10, 1} = 10 monedas, pero G {10, 1} = 7 monedas. Entonces, sabemos que el Algoritmo Codicioso no minimizará el número de monedas para el conjunto de monedas {50,25,10,1}. Por otro lado, si agregamos un nickle a este juego de monedas, G {25, 10, 5, 1} = 6 y G {10, 5, 1} = 7. Del mismo modo, para V = 10 + 5-1 = 14, obtenemos G {10, 5, 1} = 5, pero G {5,1} = 6. Entonces, sabemos, Greedy funciona para {50,25,10,5,1}.
Eso plantea la pregunta: ¿cuál debería ser la denominación de las monedas, que satisfaga el algoritmo codicioso, que resulta en el menor número de monedas del peor caso para cualquier valor del 1 al 100? La respuesta es bastante simple: 100 monedas, cada una con un valor diferente de 1 a 100. Podría decirse que esto no es muy útil, ya que la búsqueda lineal de monedas con cada transacción. Sin mencionar el costo de acuñar tantas denominaciones diferentes y rastrearlas.
Ahora, si queremos minimizar principalmente el número de denominaciones mientras minimizamos en forma secundaria el número resultante de monedas por cualquier valor de 1 a 100 producido por Greedy, entonces monedas en denominaciones de poderes de 2: {64, 32, 16, 8, 4 , 2, 1} resultan en un máximo de 6 monedas para cualquier valor 1: 100 (el número máximo de 1 en un número de siete bits cuyo valor es menor que el decimal 100). Pero esto requiere 7 denominaciones de moneda. El peor caso para las cinco denominaciones {50, 25, 10, 5, 1} es 8, que ocurre en V = 94 y V = 99. Las monedas en potencias de 3 {1, 3, 9, 27, 81} también requieren solo 5 denominaciones para ser servidas por Greedy, pero también producen un peor caso de 8 monedas con valores de 62 y 80. Finalmente, usando cualquiera de las cinco denominaciones El subconjunto de {64, 32, 16, 8, 4, 2, 1} que no puede excluir ''1'', y que satisface a Greedy, también dará como resultado un máximo de 8 monedas. Entonces hay una compensación lineal. Aumentar el número de denominaciones de 5 a 7 reduce la cantidad máxima de monedas que se necesitan para representar cualquier valor entre 1 y 100 de 8 a 6, respectivamente.
Por otro lado, si desea minimizar el número de monedas intercambiadas entre un comprador y un vendedor, suponiendo que cada una tiene al menos una moneda de cada denominación en su bolsillo, entonces este problema es equivalente al menor peso que se necesita para equilibrar cualquier peso de 1 a N libras. Resulta que la menor cantidad de monedas intercambiadas en una compra se logra si las denominaciones de moneda se dan en potencias de 3: {1, 3, 9, 27, . . .} {1, 3, 9, 27, . . .} {1, 3, 9, 27, . . .} .
Un caso fácil de recordar es que cualquier conjunto de monedas de modo que, si están ordenadas en orden ascendente, usted tiene:
coin[0] = 1
coin[i+1] >= 2 * coin[i], for all i = 0 .. N-1 in coin[N]
Entonces, un algoritmo codicioso que use tales monedas funcionará.
Dependiendo del rango que está consultando, puede haber una asignación más óptima (en términos de cantidad de monedas). Un ejemplo de esto es si está considerando el rango (6..8) y tiene las monedas <6, 7, 8> en lugar de <1, 2, 4, 8>.
La asignación de monedas más eficiente que se complete sobre N + está en igualdad con el conjunto de reglas anterior, dándole las monedas 1, 2, 4, 8 ...; que simplemente es la representación binaria de cualquier número. En cierto sentido, la conversación entre las bases es un algoritmo codicioso en sí mismo.
Una prueba de la desigualdad> = 2N es proporcionada por Max Rabkin en esta discusión: http://olympiad.cs.uct.ac.za/old/camp0_2008/day1_camp0_2008_discussions.pdf
Un conjunto que forma un matroid ( https://en.wikipedia.org/wiki/Matroid ) se puede utilizar para resolver el problema del cambio de moneda mediante el uso de un enfoque codicioso. En resumen, un matroid es un par ordenado M = (S, l) que cumple las siguientes condiciones:
- S es un conjunto finito no vacío
- l es una familia no vacía de subconjuntos de S, llamados subconjuntos independientes, de modo que si B-> l y A es un subconjunto de B, entonces A -> l
- Si A-> l, B-> l y | A | <| B |, entonces hay algún elemento x-> BA tal que AU {x} -> l
En nuestra pregunta sobre el cambio de moneda, S es un conjunto de todas las monedas en orden decreciente. Necesitamos alcanzar un valor de V por el número mínimo de monedas en S
En nuestro caso, l es un conjunto independiente que contiene todos los subconjuntos de modo que lo siguiente se cumple para cada subconjunto: la suma de los valores en ellos es <= V
Si nuestro conjunto es un matroid, entonces nuestra respuesta es el conjunto máximo A en l, en el que no se puede agregar más x
Para verificar, vemos si las propiedades de matroid se mantienen en el conjunto S = {25,15,1} donde V = 30 Ahora, hay dos subconjuntos en l: A = {25} y B = {15,15} | A | <| B |, entonces hay algún elemento x-> BA tal que AU {x} -> l (Según 3) Entonces, {25,15} debería pertenecer a l, pero es una contradicción desde 25 + 15> 30
Entonces, S no es un método matroide y, por lo tanto, codicioso no funcionará en él.
Un sistema de monedas es canónico si el número de monedas otorgadas en cambio por el algoritmo codicioso es óptimo para todas las cantidades.
Para un sistema de moneda no canónica, hay una cantidad c para la cual el algoritmo codicioso produce un número subóptimo de monedas; c se llama un contraejemplo. Un sistema de monedas es ajustado si su contraejemplo más pequeño es más grande que la moneda más grande.