Dejemos que $D$ sea un conjunto de denominaciones y $m$ el elemento más grande de $D$ . Decimos que $c$ es un contraejemplo si el algoritmo codicioso da una respuesta diferente a la óptima.
Ahora, aparentemente, si para un conjunto dado $D$ el algoritmo codicioso no devuelve una solución óptima, entonces el menor $c$ será menor que $2m-1$ .
¿Es esto realmente cierto? ¿Cómo podemos demostrarlo? Si no es así, ¿hay un rango relativamente pequeño para buscar el contraejemplo más pequeño?
El documento "Optimal Bounds for the Change-Making Problem" (de Kozen y Zaks, TCS 1994) da un límite de $x < c_M + c_{m-1}$ donde $x$ es el contraejemplo y $c_m$ y $c_{m-1}$ son la mayor y la segunda moneda más grande. Afirman que el límite es óptimo. (Sólo he ojeado el documento, y no me he tomado el tiempo de entender si esto significa automáticamente que no se puede expresar en el valor de la moneda más grande)
Jeffrey Shallit (famoso por su artículo "What this country needs is an 18c piece") publicó en 1998 una bibliografía sobre el tema: foro de matemáticas . Shallit añade " ... es un problema en el que es notoriamente fácil fácil llegar a conclusiones erróneas, algunas de las cuales incluso se han publicado ".
Buena suerte con sus investigaciones.
Recientemente se me ocurrió una solución que parecía demostrar que si se cumplen las dos condiciones dadas, el algoritmo codicioso daría la solución óptima.
a) La G.C.D (Todas las denominaciones excepto 1) = 2ª Denominación más pequeña.
b) La suma de dos denominaciones consecutivas cualesquiera debe ser menor que la tercera denominación consecutiva.
Por ejemplo. $c_2 + c_3 < c_4$ .
(Donde $c_1 = 1; c_2, c_3, c_4$ son denominaciones de monedas en orden ascendente).
Entiendo que no es una solución completa. Sin embargo, creo que si se cumplen estas 2 condiciones, el algoritmo codicioso dará la solución óptima.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Creo que se necesitan algunas suposiciones, por ejemplo, para las monedas $\{2-\sqrt{2}, 1, \sqrt{2}\}$ el primer número natural para el que el algoritmo codicioso no funciona es $3 > 2\sqrt{2}$ . Si se trata de monedas $\in \mathbb{N}$ Luego recuerdo algo similar, pero no puedo recordar la fuente. Los artículos mencionados por Hendrik parecen prometedores, sin embargo ,no estaba allí donde lo vi.