"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
Hypothesis strategies for generating Python programs, something like CSmith

hypothesmith Hypothesis strategies for generating Python programs, something like CSmith. This is definitely pre-alpha, but if you want to play with i

Zac Hatfield-Dodds 73 Dec 14, 2022
A not exist cat image generator python package

A not exist cat image generator python package

Fayas Noushad 2 Dec 03, 2021
UFDR2DIR - A script to convert a Cellebrite UFDR to the original file structure

UFDR2DIR A script to convert a Cellebrite UFDR to it's original file and directo

DFIRScience 25 Oct 24, 2022
MuMMI Core is the underlying infrastructure and generalizable component of the MuMMI framework

MuMMI Core is the underlying infrastructure and generalizable component of the MuMMI framework, which facilitates the coordination of massively parallel multiscale simulations.

4 Aug 17, 2022
Desafio Final do Mod1 do Bootcamp EDC - v2 usando a RAIS

IGTI - Bootcamp Engenheiro de Dados Cloud Módulo 1 - Desafio Final - RAIS 2020 Código do Desafio Final V2 do Bootcamp Engenheiro de Dados Cloud do IGT

Neylson Crepalde 17 Nov 02, 2022
An advanced NFT Generator

NFT Generator An advanced NFT Generator Free software: GNU General Public License v3 Documentation: https://nft-generator.readthedocs.io. Features TOD

NFT Generator 5 Apr 21, 2022
Meera 2 May 12, 2022
BlackIP-Rep is a tool designed to gather the reputation and information of Bulk IP's.

BlackIP-Rep is a tool designed to gather the reputation and information of Bulk IP's. Focused on increasing the workflow of Security Operations(SOC) team during investigation.

0LiVEr 6 Dec 12, 2022
Airbrake Python

airbrake-python Note. Python 3.4+ are advised to use new Airbrake Python notifier which supports async API and code hunks. Python 2.7 users should con

Airbrake 51 Dec 22, 2022
A Lynx that manages a group that puts the federation first.

Lynx Super Federation Management Group Lynx was created to manage your groups on telegram and focuses on the Lynx Federation. I made this to root out

Unknown 2 Nov 01, 2022
CoreSE - basic of social Engineering tool

Core Social Engineering basic of social Engineering tool. just for fun :) About First of all, I must say that I wrote such a project because of my int

Hamed Mohammadvand 7 Jun 10, 2022
A numbers check python package

A numbers check python package

Fayas Noushad 3 Nov 28, 2021
Drug Discovery App Using Lipinski's Rule-of-Five.

Drug Discovery App A Drug Discovery App Using Lipinski's Rule-of-Five. TAPIWA CHAMBOKO 🚀 About Me I'm a full stack developer experienced in deploying

tapiwa chamboko 3 Nov 08, 2022
Simple and easy to use python API for the COVID registration booking system of the math department @ unipd (torre archimede)

Simple and easy to use python API for the COVID registration booking system of the math department @ unipd (torre archimede). This API creates an interface with the official browser, with more useful

Guglielmo Camporese 4 Dec 24, 2021
Set up a sidechain for the XRPL quickly and easily

Sidechain Launch Kit Introduction This directory contains python scripts to tests and explore side chains. This document walks through the steps to se

Xpring Engineering 15 Dec 08, 2022
Use Ghidra Structs in Python

Strudra Welcome to Strudra, a way to craft Ghidra structs in python, using ghidra_bridge. Example First, init Strudra - you can pass in a custom Ghidr

Dominik Maier 27 Nov 24, 2022
It is a Blender Tool which can convert the Object Data Attributes in face corner to the UVs or Vertex Color.

Blender_ObjectDataAttributesConvertTool It is a Blender Tool which can convert the Object Data Attributes in face corner to the UVs or Vertex Color. D

Takeshi Chō 2 Jan 08, 2022
A repository for all ZenML projects that are specific production use-cases.

ZenFiles Original Image source: https://www.goodfon.com/wallpaper/x-files-sekretnye-materialy.html And naturally, all credits to the awesome X-Files s

ZenML 66 Jan 06, 2023
Audio-analytics for music-producers! Automate tedious tasks such as musical scale detection, BPM rate classification and audio file conversion.

Click here to be re-directed to the Beat Inspect Streamlit Web-App You are a music producer? Let's get in touch via LinkedIn Fundamental Analytics for

Stefan Rummer 11 Dec 27, 2022