Basandome en el algoritmo en este video de hacker rank, https://youtu.be/sn0DWI-JdNA , he intentado crear mi propio algoritmo que devuelva el valor que estoy buscando.
Basicamente, para ahorrarte 10 minutos, el algoritmo de ese video es recursivo y almacena la informacion que devuelve en cada iteracion en algun lugar, en el caso del video es un hashmap. Lo capcioso viene porque este algoritmo va ha hacer una accion diferente dependiendo de los valores actuales. de alli viene el nombre de "Memoization".
Ese algoritmo te devuelve varias combinaciones que a mi caso en particular no ayudan, asi que intente crear mi propio algoritmo.
Yo necesito encontrar el valor minimo de cambio dado una denominacion de monedas mexicana (1, 2, 5, 10). Asi que lo que busco es crear un algoritmo que devuelva la primer combinacion que encuentre y encaje.
import array
#aqui se crean 4 pilas de 1, 2, 5 y 10 monedas
uno = [1 for i in range(10)]
dos = [2 for i in range(10)]
cinco = [5 for i in range(10)]
diez = [10 for i in range(10)]
monedas = [diez, cinco, dos, uno]
#esta pila almacena las demas pilas de monedas
cont = len(monedas)-1
#contador para indices de arrays
cont2 = 0
#cuenta las iteraciones que lleva el programa
cant = int(input("dame el cambio a regresar: "))
temp = [cant]
#temporal sera una variable que se ira restando conforme avance el
#metodo en su recursion.
res = ""
# res es el diccionario donde se almacenara
# las combinaciones de monedas resultantes
#el punto de este algoritmo (cambio(etc,...)) es devolver la menor
#combinacion de monedas posibles
# este es un algoritmo que no garantiza el minimo valor logico posible
# de cambio pero intenta maximizar el tiempo
#este algoritmo va devolviendo un valor diferente cada vez que
# se itera, y este valor se va concatenando junto con otros en
# un string, que va a terminar siendo el resultado
def cambio(temp, monedas, cont, res, cont2):
if (temp >= monedas[cont]):
#si la cantidad a dividir en mas monedas es mayor que
#la moneda seleccionada en la pila de monedas
temp.insert(cont2+1, temp[cont2] -monedas[cont])
print("$",temp,"- $",monedas[cont])
print("cambio: ",res)
res = res + temp + "-"
return cambio(temp, monedas, cont, res, cont2)
if (temp <= monedas[cont]):
#si el valor a dividir en monedas es menor
#al valor de la moneda actualmente seleccionada
#en la lista
temp.insert(cont2+1, temp[cont2] - monedas[cont])
##cont2 lleva el orden de las monedas de mayor a menor
print("cambio: ",res)
res = res + temp + "-"
return cambio(temp, monedas, cont-1, res, cont2)
if (temp == monedas[cont]):
#si la cantidad a calcular es identica al valor de la moneda
#que esta seleccionada de la pila
temp.insert(cont2+1, temp[cont2] - monedas[cont])
print("cambio: ",res)
res = res + temp + "-"
return cambio(temp, monedas, cont-1, res, cont2)
if (temp == 1):
## si el cambio ya alcanzo 1
temp.insert(cont2+1, temp[cont2] - monedas[cont])
print("cambio: ",res)
return 0;
if (temp == 0):
##si el cambio ya alcanzo 0
print("cambio: ",res)
return 0
## aqui se termina la recursion en el caso de que el valor
## restante sea cero
##fin de metodo
cambio(temp, monedas, cont, res, cont2)
Al correrlo, da este error:
dame el cambio a regresar: 8
Traceback (most recent call last):
File "C:\Users\jose miguel\Desktop\python ejercicios\cambio de monedas intento
8.py", line 89, in
cambio(temp, monedas, cont, res, cont2)
File "C:\Users\jose miguel\Desktop\python ejercicios\cambio de monedas >intento 8.py", line 44, in cambio
temp.insert(cont2+1, temp[cont2] -monedas[cont])
TypeError: unsupported operand type(s) for -: 'int' and 'list'
Que pasa? porfavor ayudenme, llevo 3 meses ya atorado en este problema :(
monedas
es una lista de listas mientrastemp
almacena enteros en un principio, lo que causa el error al intentar restar una lista a un entero. Ten cuidado con la comparacióntemp >= monedas[cont]
, eso realiza una comparación entre dos listas: docs.python.org/3/tutorial/…. Aclarando lo que quieres; dada una cantidad finita de monedas de diferentes valores pretendes obtener una combinación de cambio de una cantidad dada usando el mínimo número posible de monedas? Lo de finita es importante. – FJSevilla el 29 abr. 18 a las 4:38