Asintóticos para el cambio de monedas

Dadas denominaciones de monedas, con y son números aleatorios distribuidos uniformemente en el rango . Asintóticamente, ¿para qué fracción de monedas el algoritmo codicioso genera un cambio óptimo usando este conjunto de denominaciones? $n$ $c_1=1$ $c_2<c_3<..<c_{n}$ $[2,N]$

La respuesta es conocida por 3 denominaciones ; pero ¿qué pasa con el caso general?

ds.algorithms Ganesh
fuente

Thane Plambeck planteó la probabilidad de 4 denominaciones, quien también proporcionó una expresión para la probabilidad de 3 denominaciones (consulte el enlace proporcionado por el OP). El OP hace una pregunta más general sobre el comportamiento asintótico de esta probabilidad. Quizás esto sea más adecuado para matemáticas. SE y MO, con etiquetas asintóticas. @Ganesh: ¿Cuál es su motivación TCS, o la razón de la etiqueta ds.algorithms?

András Salamon

@ Andras, este es un problema de teoría de la complejidad. Por ejemplo, si el enfoque codicioso obtiene una solución óptima, digamos el 90% del tiempo, también podría olvidar la programación dinámica y conformarme con soluciones subóptimas el 10% restante del tiempo. Quizás esto sea más apropiado en matemáticas. *, Pero la motivación radica en TCS. Finalmente, la "etiqueta correcta" se me escapó, así que pensé que ds.algorithms era la mejor aproximación.

Ganesh

Respuestas:

Esta no es una respuesta, pero tal vez esto lo guíe a usted u otra persona en la dirección correcta.

Encontré el artículo de D. Kozen y S. Zaks llamado "Límites óptimos para el problema de hacer cambios", en el que dan las condiciones para cuando el algoritmo de creación de cambio codicioso de una instancia de cambio de moneda es óptimo. Usaré su notación.

Dada una instancia de cambio de monedas de monedas distintas a función representa el número óptimo de monedas necesarias para realizar cambios para y una función $m$
$(C_{1}, C_{2}, C_{3}, \dots, C_{metro - 1}, C_{metro})$ $( c_1, c_2, c_3, \cdots, c_{m-1}, c_{m} )$ $C_{1} = 1 < C_{2} < C_{3} < \dots < C_{metro - 1} < C_{metro}$ $c_1 = 1 < c_2 < c_3 < \cdots < c_{m-1} < c_m$ $M(x)$ $x$ representa el número de monedas necesarias para realizar cambios con avidez para , entonces si $G(x)$ $x$ , existe un contraejemplo en el rango $M(x) \ne G(x)$ $C_{3} + 1 < X < C_{metro - 1} + C_{metro}$ $c_3 + 1 < x < c_{m-1} + c_m$

Continúan demostrando que

$x$ $c_3 + 1 < x < c_{m-1} + c_m$
$sol (X) \leq sol (X - C) + 1$ $G(x) \le G(x-c) + 1$ $C \in (C_{1}, C_{2}, \dots, C_{metro})$ $c \in (c_1, c_2, \cdots, c_m )$ $G(x) = M(x)$

Esto nos da una prueba "eficiente" (hasta pseudo polinomio) para determinar si una instancia de cambio de moneda es codiciosa o no.

Usando lo anterior, he realizado una breve simulación cuyos resultados se trazan en una escala de log-log a continuación

ingrese la descripción de la imagen aquí

$m$ $[1 \cdots N]$

$m=3$ $\frac{8}{3} N^{-\frac{1}{2}}$

{pag}_{metro} (norte) \propto {norte}^{- \frac{(metro - 2)}{2}}

$p_m(N) \propto N^{-\frac{(m-2)}{2} }$

$p_m(N)$ $m$ $N$

En el grande $m$ $N$

$(1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000)$ ) que no parecen estar distribuidas uniformemente. Quizás mirar otras distribuciones para generar las denominaciones de monedas arrojaría resultados no triviales en el límite del sistema grande. Por ejemplo, una distribución de la ley de potencia podría generar denominaciones de monedas que son más similares a las de EE.

usuario834
fuente