"Cambio de monedas" Change-making problem with Python, dynamic programming best solutions,

Overview

Change-making-problem / Cambio de monedas

Entendiendo el problema

Dada una cantidad de dinero y una lista de denominaciones de monedas, encontrar el número mínimo de monedas (de determinadas denominaciones) que sumen la cantidad de dinero exacta.

Es un subcaso especial del problema de la mochila

Ejemplo 1:

Pagar la cantidad de 10 usando las siguientes monedas [2,3,5,6] Tenemos 7 posibles combinaciones de cambios {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}, {5,5}

Donde la mejor combinación es {5,5} que usa la menor cantidad de monedas

Consideraciones

  • Este problema supone que todas las monedas están disponibles infinitamente.
  • Dado el caso donde la cantidad de dinero es 0 el resultado sera una lista vacia [ ]
  • Dado el caso donde no es posible pagar la cantidad con las monedas proporcionadas retornar nulo. Ejemplo cantidad=5 monedas[2,4]

Solucion 1

La primera solución contempla todas las posibles combinaciones, podemos implementarla dividiendo en pequeños subproblemas y aplicando recursividad.

Por cada moneda hacemos una resta de la cantidad de dinero menos el valor de la moneda de esta forma obtenemos un punto de inicio de cada combinación y dividimos el problema en subproblemas. Aqui podemos aplicar recursividad y continuar haciendo las restas mientras la cantidad a pagar disminuye y llega a 0, de esta forma obtenemos todas las posibles combinaciones. En esta parte necesitamos hacer una validación para detener la iteración cuando la cantidad llegue a igual o menor que 0 (Si llega a 0 sabemos que es una posible solución).

Ejemplo de divición de subproblemas para el caso, monedas: [1,2,3] y cantidad de 5 subPrograms

Seguido de esto necesitamos encontrar la mejor solución que úse la menor cantidad de monedas, necesitamos hacer una comparacion para obtener la mejor solución de cada suproblema, guardarla y retornar la combinacion con menor cantidad de monedas por cada nivel (cada vez que disminuimos la cantidad a pagar). Por eso esta primera solución es una estrategia de análisis top-down (de arriba hacia abajo)

#monedas debe ser un arreglo de enteros, cantidad debe ser un entero no menor que 0
def makeChange(monedas, cantidad):
    if cantidad == 0: #Validación cuando lleguemos a la cantidad 0
        return []
    if cantidad < 0: #Validación para saber que llegamos a una cantidad negativa que no se puede pagar
        return None
    resultadoOptimo = None #declaramos e inicializamos el resultadoOptimo que retornaremos
    for moneda in monedas: #iteramos sobre cada moneda
        #llamamos a makeChange para obtener una posible solución
        #Restamos el valor actual de moneda para dividir en subproblemas
        combinacion = makeChange(monedas, cantidad - moneda) #Aqui podemos obtener [], None o una posible combinación
        if combinacion != None: #Validación para saber que es una posible combinacion
            candidata = combinacion + [moneda] #Validación para saber que es una posible combinacion
            #Comparamos si la solucion candidata es mejor que el resultadoOptimo actual lo remplazamos
            if (resultadoOptimo is None or len(candidata) < len(resultadoOptimo)):
                resultadoOptimo = candidata
    return resultadoOptimo

img

Notemos que tenemos subproblemas que se repiten, dada la recursividad y el uso de todas las combinaciones posibles, esta solucion tiene una complejidad exponencial y poco rendimiento.

Ejemplo 1/version 2:

Podemos guardar los resultados para reducir la complejidad a O(nv), n es la cantidad de monedas y v la cantidad de pasos, para esto podemos utilizar el módulo functools que nos proporciona un método llamado lru_cache que recibe una función de la cual vamos a poder guardar el resultado o lo que retorna, de esta forma si llamamos a una determinada función con los mismos argunmentos varias veces retornan el valor guardado en memoria sin ejecutar dicha función.

from functools import lru_cache #import del módulo
def makeChange(monedas, cantidad): #Necesitamos una funcion como envolvente para manejar las monedas
    @lru_cache(maxsize=None, typed=False) #inicializamos la cache sin límite para la función helper
    def helper(cantidad): #Guardamos el resultado para cada cantidad
        if cantidad == 0:
            return []
        if cantidad < 0:
            return None
        resultadoOptimo = None
        for moneda in monedas:
            combinacion = helper(cantidad - moneda)
            if combinacion != None:
                candidata = combinacion + [moneda]
                if (resultadoOptimo is None or len(candidata) < len(resultadoOptimo)):
                    resultadoOptimo = candidata
        return resultadoOptimo
    return helper(cantidad)

img

Cada solución es manejada como un módulo, el archivo main.py junta y llama cada solución y calcula su tiempo de ejecución, por defecto maneja el caso de monedas=[1,2,3,4,5,6,7,8,9] y cantidad=20 la cual se puede cambiar en main.py

    //with python 3
    python main.py

Solucion 2, bottom-up O(nv)

La segunda solución contempla la estrategia de análisis bottom-up, guiandonos de la primera solución empezaremos con la cantidad de 0 agregando las posibles combinaciones de monedas hasta llegar a la cantidad final.

Owner
Juan Antonio Ayola Cortes
Student | Software Engineering
Juan Antonio Ayola Cortes
Procedurally generated Oblique Strategies for writing your own Oblique Strategies

Procedurally generated Oblique Strategies for writing your own Oblique Strategies.

Gordon Brander 13 Aug 17, 2022
An OBS script to fuze files together

OBS TEXT FUZE Fuze text files and inject the output into a text source. The Index file directory should be a list of file directorys for the text file

SuperZooper3 1 Dec 27, 2021
Library for mocking AsyncIOMotorClient built on top of mongomock.

mongomock-motor Best effort mock for AsyncIOMotorClient (Database, Collection, e.t.c) built on top of mongomock library. Example / Showcase from mongo

Michael Kryukov 43 Jan 04, 2023
Wordless - the #1 app for helping you cheat at Wordle, which is sure to make you popular at parties

Wordless Wordless is the #1 app for helping you cheat at Wordle, which is sure t

James Kirk 7 Feb 04, 2022
The worst and slowest programming language you have ever seen

VenumLang this is a complete joke EXAMPLE: fizzbuzz in venumlang x = 0

Venum 7 Mar 12, 2022
Architectural Patterns implementation by using notification handler module prototype

This repository covers singleton, indirection, factory, adaptor, mediator patterns in python language by using university hypothetical notification module prototype. The code is just for demonstratin

Muhammad Umair 2 Jan 08, 2022
Collection of system-wide scripts that I use on my Gentoo

linux-scripts Collection of scripts that I use on my Gentoo machine. I tend to put all scripts in /scripts directory. It is not likely that you would

Xoores 1 Jan 09, 2022
A rough GSL work DynSAGE of my graduation project

DynSAGE Codes w.r.t DynSAGE-Diffuse can be found in function apply_dyn_model_v2 of src/utils.py. The training entrance is Line 144 - 155 of src/main.p

Yuhan Wang 3 Mar 22, 2022
Developer guide for Hivecoin project

Hivecoin-developer Developer guide for Hivecoin project. Install Content are writen in reStructuredText (RST) and rendered with Sphinx. Much of the co

tweetyf 1 Nov 22, 2021
Blender Add-on That Provides Quick Access to Render Controls

Blender Render Buttons Blender Add-on That Provides Quick Access to Render Controls A Blender 3.0 compatablity update of Blender2.8x-RenderButton v0.0

Don Schnitzius 3 Oct 18, 2022
Ml-design-patterns - Source code accompanying O'Reilly book: Machine Learning Design Patterns

This is not an official Google product ml-design-patterns Source code accompanying O'Reilly book: Title: Machine Learning Design Patterns Authors: Val

Google Cloud Platform 1.5k Jan 05, 2023
A simple panel with IP, CNPJ, CEP and PLACA queries

Painel mpm Um painel simples com consultas de IP, CNPJ, CEP e PLACA Início 🌐 apt update && apt upgrade -y pkg i python git pip install requests Insta

MrDiniz 4 Nov 04, 2022
AlexaUsingPython - Alexa will pay attention to your order, as: Hello Alexa, play music, Hello Alexa

AlexaUsingPython - Alexa will pay attention to your order, as: Hello Alexa, play music, Hello Alexa, what's the time? Alexa will pay attention to your order, get it, and afterward do some activity as

Abubakar Sattar 10 Aug 18, 2022
The mock Pokemon Environment I built in 2019 to study Reinforcement Learning + Pokemon

ghetto-pokemon-rl-environment ##NOT MAINTAINED! Fork and maintain yourself. Environment I made back in 2019 to use Pokemon to practice reinforcement l

2 Dec 09, 2021
A Classroom Engagement Platform

Project Introduction This is project introduction Setup Setting up Postgres This is the most tricky part when setting up the application. You will nee

Santosh Kumar Patro 1 Nov 18, 2021
Checks for Vaccine Availability at your district and notifies you using E-mail, subscribe to our website.

Vaccine Availability Notifier Project Description Checks for Vaccine Availability at your district and notifies you using E-mail every 10 mins. Kindly

Farhan Hai Khan 19 Jun 03, 2021
an opensourced roblox group finder writen in python 100% free and virus-free

Roblox-Group-Finder an opensourced roblox group finder writen in python 100% free and virus-free note : if you don't want install python or just use w

mollomm1 1 Nov 11, 2021
An implementation of Ray Tracing in One Weekend using Taichi

又一个Taichi语言的Ray Tracer 背景简介 这个Ray Tracer基本上是照搬了Peter Shirley的第一本小书Ray Tracing in One Weekend,在我写的时候参考的是Version 3.2.3这个版本。应该比其他中文博客删改了不少内容。果然Peter Shir

张皓 30 Nov 21, 2022
Gives criticality score for an open source project

Open Source Project Criticality Score (Beta) This project is maintained by members of the Securing Critical Projects WG. Goals Generate a criticality

Open Source Security Foundation (OpenSSF) 1.1k Dec 23, 2022
Exploiting Linksys WRT54G using a vulnerability I found.

Exploiting Linksys WRT54G Exploit # Install the requirements. pip install -r requirements.txt ROUTER_HOST=192.169.1.1 ROUTER_USERNAME=admin ROUTER_P

Elon Gliksberg 31 May 29, 2022