1102_coins.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "1102-coins.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPWkz62xO4GH/QhB4ttpFgW",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/lmcanavals/acomplex/blob/main/1102_coins.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "X82QbiyGroWd"
      },
      "outputs": [],
      "source": [
        "def greedycoins(p, d):\n",
        "    coins = []\n",
        "    i = len(d) - 1\n",
        "    while p > 0:\n",
        "        while d[i] > p:\n",
        "            i -= 1\n",
        "        coins.append(d[i])\n",
        "        p -= d[i]\n",
        "    return coins"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "d = [1, 5, 10, 20, 50]\n",
        "print(greedycoins(40, d))\n",
        "print(greedycoins(85, d))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aXCd4MCfsVjp",
        "outputId": "333f90a9-2a3e-4c9c-996a-9ed0e89868b9"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[20, 20]\n",
            "[50, 20, 10, 5]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "d = [1, 5, 10, 20, 25, 50]\n",
        "print(greedycoins(40, d))\n",
        "print(greedycoins(85, d))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2Qq9hokLsaBo",
        "outputId": "e4f5d608-4465-41df-8b7f-5d9cd6933944"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[25, 10, 5]\n",
            "[50, 25, 10]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Dynamic Programming"
      ],
      "metadata": {
        "id": "pFudJBgPtlCz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def dpcoins(p, d):\n",
        "    C = [0]*(p + 1)\n",
        "    S = [0]*(p + 1)\n",
        "    for pi in range(1, p + 1):\n",
        "        mind = 0\n",
        "        for k in range(len(d)):\n",
        "            if d[k] > pi: break\n",
        "            if C[pi - d[k]] < C[pi - d[mind]]:\n",
        "                mind = k\n",
        "        C[pi] = C[pi - d[mind]] + 1\n",
        "        S[pi] = d[mind]\n",
        "\n",
        "    coins = []\n",
        "    while p > 0:\n",
        "        coins.append(S[p])\n",
        "        p -= S[p]\n",
        "    \n",
        "    return coins\n"
      ],
      "metadata": {
        "id": "kIUwmx0rsnHy"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "d = [1, 5, 10, 20, 50]\n",
        "print(dpcoins(40, d))\n",
        "print(dpcoins(85, d))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UsNxu1CZuRGM",
        "outputId": "a0e8a6b8-ce0a-4243-f381-acdc8938831b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[20, 20]\n",
            "[5, 10, 20, 50]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "d = [1, 5, 10, 20, 25, 50]\n",
        "print(dpcoins(40, d))\n",
        "print(dpcoins(85, d))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zK8hU51jueOs",
        "outputId": "b22ed197-20ef-48b4-e95c-c3d4c98e9877"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[20, 20]\n",
            "[10, 25, 50]\n"
          ]
        }
      ]
    }
  ]
}