arrays - vale - Cambio de moneda con memoria limitada para números de hasta mil millones
tipo de cambio euro dolar wells fargo (2)
Me enfrenté a este problema en un entrenamiento. Es decir, hemos dado N valores diferentes ( N<= 100 ). Llamemos a esta matriz A[N] , para esta matriz A estamos seguros de que tenemos 1 en la matriz y A[i] ≤ 10 9 . En segundo lugar, hemos dado el número S donde S ≤ 10 9 .
Ahora tenemos que resolver el problema de la moneda clásica con estos valores. En realidad, necesitamos encontrar el número mínimo de elementos que sumarán exactamente S Cada elemento de A se puede usar un número infinito de veces.
Tiempo límite: 1 seg.
Límite de memoria: 256 MB
Ejemplo:
S = 1000, N = 10
A[] = {1,12,123,4,5,678,7,8,9,10}. The result is 10.
1000 = 678 + 123 + 123 + 12 + 12 + 12 + 12 + 12 + 12 + 4
Lo que he intentado
Traté de resolver esto con la técnica clásica de problemas de la programación dinámica de monedas, pero usa demasiada memoria y da un límite de memoria excedido.
No puedo averiguar qué debemos mantener sobre esos valores. Gracias por adelantado.
Aquí están los casos de prueba en pareja que no se pueden resolver con el problema clásico de la moneda dp.
S = 1000000000 N = 100
1 373241370 973754081 826685384 491500595 765099032 823328348 462385937
251930295 819055757 641895809 106173894 898709067 513260292 548326059
741996520 959257789 328409680 411542100 329874568 352458265 609729300
389721366 313699758 383922849 104342783 224127933 99215674 37629322
230018005 33875545 767937253 763298440 781853694 420819727 794366283
178777428 881069368 595934934 321543015 27436140 280556657 851680043
318369090 364177373 431592761 487380596 428235724 134037293 372264778
267891476 218390453 550035096 220099490 71718497 860530411 175542466
548997466 884701071 774620807 118472853 432325205 795739616 266609698
242622150 433332316 150791955 691702017 803277687 323953978 521256141
174108096 412366100 813501388 642963957 415051728 740653706 68239387
982329783 619220557 861659596 303476058 85512863 72420422 645130771
228736228 367259743 400311288 105258339 628254036 495010223 40223395
110232856 856929227 25543992 957121494 359385967 533951841 449476607
134830774
OUTPUT FOR THIS TEST CASE: 5
S = 999865497 N = 7
1 267062069 637323855 219276511 404376890 528753603 199747292
OUTPUT FOR THIS TEST CASE: 1129042
S = 1000000000 N = 40
1 12 123 4 5 678 7 8 9 10 400 25 23 1000 67 98 33 46 79 896 11 112 1223 412
532 6781 17 18 19 170 1400 925 723 11000 607 983 313 486 739 896
OUTPUT FOR THIS TEST CASE: 90910
( NOTA: Actualizado y editado para mayor claridad. Análisis de complejidad agregado al final. )
Bien, aquí está mi solución, incluidas mis correcciones a los problemas de rendimiento encontrados por @PeterdeRivaz. He probado esto con todos los casos de prueba proporcionados en la pregunta y los comentarios y termina todo en menos de un segundo (bueno, 1.5s en un caso), usando principalmente solo la memoria para el caché de resultados parciales (supongo unos 16MB).
En lugar de utilizar la solución tradicional de DP (que es demasiado lenta y requiere demasiada memoria), utilizo una búsqueda combinatoria de Depth-First, Greedy-First con poda con los mejores resultados actuales. Me sorprendió (muy) que esto funcione tan bien como lo hace, pero aún sospecho que se podrían construir conjuntos de pruebas que tomarían una cantidad de tiempo exponencial en el peor de los casos.
Primero, hay una función maestra que es lo único que el código de llamada necesita llamar. Maneja toda la configuración e inicialización y llama a todo lo demás. (todo el código es C #)
// Find the min# of coins for a specified sum
int CountChange(int targetSum, int[] coins)
{
// init the cache for (partial) memoization
PrevResultCache = new PartialResult[1048576];
// make sure the coins are sorted lowest to highest
Array.Sort(coins);
int curBest = targetSum;
int result = CountChange_r(targetSum, coins, coins.GetLength(0)-1, 0, ref curBest);
return result;
}
Debido al problema de los casos de prueba planteados por @PeterdeRivaz, también he agregado un caché de resultados parciales para manejar cuando hay grandes números en N [] que están muy juntos.
Aquí está el código para el caché:
// implement a very simple cache for previous results of remainder counts
struct PartialResult
{
public int PartialSum;
public int CoinVal;
public int RemainingCount;
}
PartialResult[] PrevResultCache;
// checks the partial count cache for already calculated results
int PrevAddlCount(int currSum, int currCoinVal)
{
int cacheAddr = currSum & 1048575; // AND with (2^20-1) to get only the first 20 bits
PartialResult prev = PrevResultCache[cacheAddr];
// use it, as long as it''s actually the same partial sum
// and the coin value is at least as large as the current coin
if ((prev.PartialSum == currSum) && (prev.CoinVal >= currCoinVal))
{
return prev.RemainingCount;
}
// otherwise flag as empty
return 0;
}
// add or overwrite a new value to the cache
void AddPartialCount(int currSum, int currCoinVal, int remainingCount)
{
int cacheAddr = currSum & 1048575; // AND with (2^20-1) to get only the first 20 bits
PartialResult prev = PrevResultCache[cacheAddr];
// only add if the Sum is different or the result is better
if ((prev.PartialSum != currSum)
|| (prev.CoinVal <= currCoinVal)
|| (prev.RemainingCount == 0)
|| (prev.RemainingCount >= remainingCount)
)
{
prev.PartialSum = currSum;
prev.CoinVal = currCoinVal;
prev.RemainingCount = remainingCount;
PrevResultCache[cacheAddr] = prev;
}
}
Y aquí está el código para la función recursiva que realiza el conteo real:
/*
* Find the minimum number of coins required totaling to a specifuc sum
* using a list of coin denominations passed.
*
* Memory Requirements: O(N) where N is the number of coin denominations
* (primarily for the stack)
*
* CPU requirements: O(Sqrt(S)*N) where S is the target Sum
* (Average, estimated. This is very hard to figure out.)
*/
int CountChange_r(int targetSum, int[] coins, int coinIdx, int curCount, ref int curBest)
{
int coinVal = coins[coinIdx];
int newCount = 0;
// check to see if we are at the end of the search tree (curIdx=0, coinVal=1)
// or we have reached the targetSum
if ((coinVal == 1) || (targetSum == 0))
{
// just use math get the final total for this path/combination
newCount = curCount + targetSum;
// update, if we have a new curBest
if (newCount < curBest) curBest = newCount;
return newCount;
}
// prune this whole branch, if it cannot possibly improve the curBest
int bestPossible = curCount + (targetSum / coinVal);
if (bestPossible >= curBest)
return bestPossible; //NOTE: this is a false answer, but it shouldnt matter
// because we should never use it.
// check the cache to see if a remainder-count for this partial sum
// already exists (and used coins at least as large as ours)
int prevRemCount = PrevAddlCount(targetSum, coinVal);
if (prevRemCount > 0)
{
// it exists, so use it
newCount = prevRemCount + targetSum;
// update, if we have a new curBest
if (newCount < curBest) curBest = newCount;
return newCount;
}
// always try the largest remaining coin first, starting with the
// maximum possible number of that coin (greedy-first searching)
newCount = curCount + targetSum;
for (int cnt = targetSum / coinVal; cnt >= 0; cnt--)
{
int tmpCount = CountChange_r(targetSum - (cnt * coinVal), coins, coinIdx - 1, curCount + cnt, ref curBest);
if (tmpCount < newCount) newCount = tmpCount;
}
// Add our new partial result to the cache
AddPartialCount(targetSum, coinVal, newCount - curCount);
return newCount;
}
Análisis:
Memoria:
El uso de la memoria es bastante fácil de determinar para este algoritmo. Básicamente solo hay el caché de resultados parciales y la pila. El caché se fija en appx. 1 millón de entradas multiplicado por el tamaño de cada entrada (3 * 4 bytes), aproximadamente 12 MB. La pila está limitada aO(N) , por lo que juntos, la memoria claramente no es un problema. UPC:
La complejidad del tiempo de ejecución de este algoritmo comienza siendo difícil de determinar y luego se vuelve más difícil, así que discúlpeme porque aquí hay muchos movimientos de mano. Intenté buscar un análisis del problema de la fuerza bruta (búsqueda combinatoria de sumas de valores base de N * kn que suman S), pero no mucho más. Lo poco que se tendía a decir que eraO(N^S) , que es claramente demasiado alto. Creo que una estimación más justa es O(N^(S/N)) o posiblemente O(N^(S/AVG(N)) o incluso O(N^(S/(Gmean(N))) donde Gmean(N) es la media geométrica de los elementos de N []. Esta solución comienza con la búsqueda combinatoria de fuerza bruta y luego la mejora con dos optimizaciones significativas. La primera es la poda de sucursales en función de las estimaciones de los mejores resultados posibles para esa rama en comparación con el mejor resultado que ya ha encontrado. Si los estimadores de los mejores casos fuesen perfectamente precisos y el trabajo para las sucursales estuviera perfectamente distribuido, esto significaría que si encontramos un resultado mejor que el 90% de los otros casos posibles, la poda eliminaría efectivamente el 90% del trabajo de ese punto en adelante Para resumir aquí la historia larga, esto debería resolver que la cantidad de trabajo que queda después de la poda debería reducirse armónicamente a medida que avanza. Suponiendo que se debe aplicar algún tipo de suma / integración para obtener un total de trabajo, me parece que esto funciona con un logaritmo del trabajo original. Así que llamémoslo O(Log(N^(S/N)) , o O(N*Log(S/N)) que es bastante bueno. (Aunque O(N*Log(S/Gmean(N))) es probablemente mas preciso).
Sin embargo, hay dos agujeros obvios con esto. Primero, es cierto que los estimadores de mejor caso no son perfectamente precisos y, por lo tanto, no se podarán tan eficazmente como se supone anteriormente, pero esto es algo contrabalanceado por el ordenamiento codicioso de las sucursales, que brinda las mejores oportunidades para Encontrar mejores soluciones al principio de la búsqueda que aumentan la efectividad de la poda.
El segundo problema es que el mejor estimador de caso funciona mejor cuando los diferentes valores de N están muy separados. Específicamente, si |(S/n2 - S/n1)| > 1 |(S/n2 - S/n1)| > 1 para cualquiera de los 2 valores en N, entonces se vuelve casi perfectamente efectivo. Para valores de N menores que SQRT (S), incluso dos valores adyacentes (k, k + 1) están lo suficientemente separados como para que se aplique esta regla. Sin embargo, para aumentar los valores por encima de SQRT (S), se abre una ventana, de modo que cualquier número de valores N dentro de esa ventana no podrá podarse entre sí. El tamaño de esta ventana es aproximadamente K / SQRT (S). Entonces, si S = 10 ^ 9, cuando K es alrededor de 10 ^ 6, esta ventana tendrá casi 30 números de ancho. Esto significa que N [] podría contener 1 más cada número desde 1000001 hasta 1000029 y la optimización de la poda no proporcionaría casi ningún beneficio.
Para abordar esto, agregué el caché de resultados parciales que permite la memorización de las sumas parciales más recientes hasta el objetivo S. Esto se beneficia del hecho de que cuando los valores de N están cerca, tenderán a tener un número extremadamente alto. De duplicados en sus sumas. Lo mejor que puedo imaginar, esta efectividad es aproximadamente N veces la raíz J-th del tamaño del problema donde J = S/K y K es una medida del tamaño promedio de los valores N (Gmean (N) es probablemente la mejor estimación). Si aplicamos esto a la búsqueda combinatoria de fuerza bruta, asumiendo que la poda es ineficaz, obtenemos O((N^(S/Gmean(N)))^(1/Gmean(N))) , que creo que también es O(N^(S/(Gmean(N)^2))) .
Así que, en este punto, haga su elección. Sé que esto es realmente incompleto, e incluso si es correcto, todavía es muy sensible a la distribución de los valores N, por lo que hay mucha variación.
[He reemplazado la idea anterior acerca de las operaciones de bits porque parece llevar demasiado tiempo]
Una idea algo loca e incompleta pero puede funcionar.
Comencemos con la introducción de f(n,s) que devuelve el número de combinaciones en las que s puede componerse de n monedas.
Ahora, ¿cómo f(n+1,s) está relacionado con f(n) ?
Una de las posibles formas de calcularlo es:
f(n+1,s)=sum[coin:coins]f(n,s-coin)
Por ejemplo, si tenemos monedas 1 y 3,
f(0,)=[1,0,0,0,0,0,0,0] - con cero monedas solo podemos tener una suma de cero
f(1,)=[0,1,0,1,0,0,0,0] - lo que podemos tener con una moneda
f(2,)=[0,0,1,0,2,0,1,0] - lo que podemos tener con dos monedas
Podemos reescribirlo un poco diferente:
f(n+1,s)=sum[i=0..max]f(n,si)*a(i)
a(i)=1 si tenemos la moneda i 0 de lo contrario
Lo que tenemos aquí es convolución: f(n+1,)=conv(f(n,),a)
https://en.wikipedia.org/wiki/Convolution
Calcularlo como sugiere la definición da O(n^2)
Pero podemos usar la transformada de Fourier para reducirla a O (n * log n).
https://en.wikipedia.org/wiki/Convolution#Convolution_theorem
Así que ahora tenemos una forma más o menos barata de averiguar qué números son posibles con n monedas sin ir incrementalmente, simplemente calcule n-th potencia n-th de F(a) y aplique la transformada de Fourier inversa.
Esto nos permite realizar una búsqueda binaria que puede ayudar a manejar los casos cuando la respuesta es grande.
Como dije, la idea es incompleta: por ahora no tengo idea de cómo combinar la representación de bits con las transformadas de Fourier (para satisfacer la restricción de memoria) y si encajaremos en 1 segundo en cualquier CPU "normal" ...