Algoritmo montos posibles (sobre) pagados por un precio específico, según las denominaciones

Question

En un proyecto actual, las personas pueden solicitar los productos entregados a su puerta y elegir 'pago contra entrega' como una opción de pago. Para asegurarse de que el repartidor tenga suficiente cambio, se le pide a los clientes que ingresen el monto que pagarán (por ejemplo, la entrega es 48,13, pagarán con 60, - (3 * 20, -)). Ahora, si dependiera de mí, lo convertiría en un campo libre, pero aparentemente los altos mandos decidieron que debería ser una selección basada en las denominaciones disponibles, sin dar cantidades que darían como resultado un conjunto de denominaciones que podría ser más pequeño.

Ejemplo:

denominations = [1,2,5,10,20,50] 
price = 78.12 
possibilities: 
    79 (multitude of options), 
    80 (e.g. 4*20) 
    90 (e.g. 50+2*20) 
    100 (2*50) 

Es internacional, por lo que las denominaciones podrían cambiar, y el algoritmo debe basarse en esa lista.

Lo más cerca que he llegado que parece funcionar es la siguiente:

for all denominations in reversed order (large=>small) 
    add ceil(price/denomination) * denomination to possibles 
    baseprice = floor(price/denomination) * denomination; 
    for all smaller denominations as subdenomination in reversed order 
     add baseprice + (ceil((price - baseprice)/subdenomination) * subdenomination) to possibles 
    end for 
end for 
remove doubles 
sort 

Es parece a trabajar, pero esto ha surgido después de tratar violentamente todo tipo de algoritmos compactos, y no puedo defender qué funciona, lo que podría llevar a que algunos países nuevos o de vanguardia obtengan opciones incorrectas, y genera algunas cantidades importantes de dobles.

Como esto probablemente no es un problema nuevo, y Google et al. No pude darme una respuesta, salvo por un montón de páginas que calculan cómo hacer un cambio exacto. Pensé que podría preguntar SO: ¿Ya resolvió este problema? ¿Qué algoritmo? ¿Alguna prueba de que siempre funcionará?

Answer 1

Su una aplicación del algoritmo voraz http://mathworld.wolfram.com/GreedyAlgorithm.html (Un algoritmo utilizado para construir de forma recursiva un conjunto de objetos de las partes constituyentes más pequeñas posibles)

Pseudocódigo

list={1,2,5,10,20,50,100} (*ordered *) 
while list not null 
    found_answer = false 
    p = ceil(price) (* assume integer denominations *) 
    while not found_answer 
     find_greedy (p, list) (*algorithm in the reference above*) 
     p++ 
    remove(first(list)) 

EDITAR> algunas iteraciones son tonterías>

list={1,2,5,10,20,50,100} (*ordered *) 
p = ceil(price) (* assume integer denominations *) 
while list not null 
    found_answer = false 
    while not found_answer 
     find_greedy (p, list) (*algorithm in the reference above*) 
     p++ 
    remove(first(list)) 

EDITAR>

He encontrado una mejora debido a Pearson en el algoritmo codicioso. Su O (N^3 log Z), donde N es el número de denominaciones y Z es la cuenta más grande del conjunto.

Puede encontrarlo en http://library.wolfram.com/infocenter/MathSource/5187/

Answer 2

Puede generar en la base de datos todas las combinaciones posibles de monedas y papel (no estoy bien en inglés) y cada fila contiene la suma de esta combinación.

Tener esta base de datos se puede obtener toda sencilla posible pagado en exceso por una consulta,

WHERE sum >= cost and sum <= cost + epsilon 

Algunas palabras sobre épsilon, hmm .. se pueden asignar otras de valor de coste? Quizás el 10% del costo + 10 dólares ?:

WHERE sum >= cost and sum <= cost * 1.10 + 10 

estructura de la tabla debe tener el número de columnas que representan el número de monedas y tipo de papel. El valor de cada columna tiene el número de ocurrencias de este tipo de artículo pagado.

Esta no es una solución óptima y rápida de este problema, pero fácil y simple de implementar. Pienso en una mejor solución para esto.

---

Otra forma en que puede para cost- cost + epsilon y para cada valor, calcular menor número posible de los artículos pagados para cada uno. Tengo algoritmo para eso.Puede hacer esto con este algoritmo, pero esto es en C++:

int R[10000]; 
sort(C, C + coins, cmp); 

R[0]=0; 

for(int i=1; i <= coins_weight; i++) 
{ 
    R[i] = 1000000; 
    for (int j=0; j < coins; j++) 
    { 
     if((C[j].weight <= i) && ((C[j].value + R[i - C[j].weight]) < R[i])) 
     { 
      R[i] = C[j].value + R[i - C[j].weight]; 
     } 
    } 
} 

return R[coins_weight];