"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
A web application which you can search, buy or sell shares with current prices which provided by IEX.

CS50 - Stock Exchange A web application which you can search, buy or sell shares with current prices which provided by IEX. Table of Contents Setup St

1 May 28, 2022
Algorand Python API examples

Algorand-Py Algorand Python API examples This repo will hold example scripts to monitor activities on Algorand main net. You can: Monitor your assets

Karthik Dutt 2 Jan 23, 2022
A fishing bot script written in Python!

A fishing bot script written in Python!

Anel Drocic 3 Nov 03, 2021
A submodule of rmcrkd/ODE-Uniqueness

Heston-ODE This repo contains the Heston-related code that accompanies the article One-sided maximal uniqueness for a class of spatially irregular ord

0 Jan 05, 2022
Utility/Raiding selfbot made by Shell and Roover.

Utility/Raiding selfbot made by Shell and Roover. We are open to suggestions and ideas.

Shell 2 Dec 08, 2021
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
A service to display a quick summary of a project on GitHub.

A service to display a quick summary of a project on GitHub. Usage 📖 Paste the code below with details filled in as specified below into your Readme.

Rohit V 8 Dec 06, 2022
Structured, dependable legos for starknet development.

Structured, dependable legos for starknet development.

Alucard 127 Nov 23, 2022
Hands-on machine learning workshop

emb-ntua-workshop This workshop discusses introductory concepts of machine learning and data mining following a hands-on approach using popular tools

ISSEL Soft Eng Team 12 Oct 30, 2022
Код файнтюнинга оригинального CLIP на русский язык

О чем репозиторий В этом репозитории представлен способ файтюнить оригинальный CLIP на новый язык Почему модель не видит женщину и откуда на картинке

Valentina Biryukova 7 Feb 06, 2022
A python program, imitating functionalities of a banking system

A python program, imitating functionalities of a banking system, in order for users to perform certain operations in a bank.

Moyosore Weke 1 Nov 26, 2021
Module to align code with thoughts of users and designers. Also magically handles navigation and permissions.

This readme will introduce you to Carteblanche and walk you through an example app, please refer to carteblanche-django-starter for the full example p

Eric Neuman 42 May 28, 2021
Various hdas (Houdini Digital Assets)

aaTools My various assets for Houdini "ms_asset_loader" - Custom importer assets from Quixel Bridge "asset_placer" - Tool for placment sop geometry on

9 Dec 19, 2022
Saturne best tools pour baiser tout le système de discord

Installation | Important | Discord 🌟 Comme Saturne est gratuit, les dons sont vraiment appréciables et maintiennent le développement! Caractéristique

GalackQSM 8 Oct 02, 2022
Pequenos programas variados que estou praticando e implementando, leia o Read.me!

my-small-programs Pequenos programas variados que estou praticando e implementando! Arquivo: automacao Automacao de processos de rotina com código Pyt

Léia Rafaela 43 Nov 22, 2022
python based clash stars made by grade 7 and 5

clash_stars python based clash stars made by grade 7 and 5 How to play: PLAYER ONE (LEFT PLAYER) Move: W,A,S,D Shoot: SHIFT PLAYER TWO (RIGHT PLAYER)

5 Oct 22, 2021
🔩 Like builtins, but boltons. 250+ constructs, recipes, and snippets which extend (and rely on nothing but) the Python standard library. Nothing like Michael Bolton.

Boltons boltons should be builtins. Boltons is a set of over 230 BSD-licensed, pure-Python utilities in the same spirit as — and yet conspicuously mis

Mahmoud Hashemi 6k Jan 06, 2023
This repo presents you the official code of "VISTA: Boosting 3D Object Detection via Dual Cross-VIew SpaTial Attention"

VISTA VISTA: Boosting 3D Object Detection via Dual Cross-VIew SpaTial Attention Shengheng Deng, Zhihao Liang, Lin Sun and Kui Jia* (*) Corresponding a

104 Dec 29, 2022
Project in which we modelise an Among Us problem using graph theories.

Python-AmongUsProblem Project in which we modelise an Among Us problem using graph theories. The rules are as following: Total of 100 players 10 playe

Gabriel Shenouda 1 Feb 09, 2022
This is a library to do functional programming in Python.

Fpylib This is a library to do functional programming in Python. Index Fpylib Index Features Intelligents Ranges with irange Lazyness to functions Com

Fabián Vega Alcota 4 Jul 17, 2022