coin_change_nonrepeat.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Making Change Without Repeats (DPV 6.18) #"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Problem ###\n",
    "\n",
    "We are given coin denominations $x_1, x_2 , . . . , x_n$, and we want to know if we can make change for a value $v$. \n",
    "\n",
    "We are allowed to use each coin denomination at most once. \n",
    "\n",
    "**Example:**\n",
    "\n",
    "*Denominations: 1, 5, 10, 20* \n",
    "\n",
    "We can make change for $16 = 1 + 15$ and for $31 = 1 + 10 + 20$ but not for 40 because we can't use 20 twice)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1: Define subproblem in words ###\n",
    "\n",
    "The entry $T(i, j)$ indicates whether we can make change for $j$ with the first $i$ denominations (i.e. denominations $x_1$ to $x_i$). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 2: Find the recurrence relation ###\n",
    "\n",
    "$$\n",
    "T(i, j) = \\left\\{\\begin{aligned}\n",
    "&True &&: j = x_i\\\\\n",
    "&True &&: T(i-1,j-x_i) = True\\\\\n",
    "&T(i-1, j) &&: otherwise\n",
    "\\end{aligned}\n",
    "\\right.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 3: Translate into code ###"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1]]\n",
      "Q. Can we make change for 30 with denominations [1, 5, 10, 10, 10, 25]?\n",
      "A. True\n",
      "[[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]\n",
      " [0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1]\n",
      " [0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1]\n",
      " [0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1]]\n",
      "Q. Can we make change for 30 with denominations [25, 10, 5, 10, 10, 1]?\n",
      "A. True\n",
      "[[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1]]\n",
      "Q. Can we make change for 16 with denominations [1, 5, 10, 20]?\n",
      "A. True\n",
      "[[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1]]\n",
      "Q. Can we make change for 31 with denominations [1, 5, 10, 20]?\n",
      "A. True\n",
      "[[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      "  0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      "  0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      "  0 0 0]\n",
      " [1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0\n",
      "  0 0 0]]\n",
      "Q. Can we make change for 40 with denominations [1, 5, 10, 20]?\n",
      "A. False\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def coin_change_no_repeat(v, n):\n",
    "\n",
    "    # The table T\n",
    "    table = np.zeros((len(n), v), dtype=int)\n",
    "    \n",
    "    # For every denomination...\n",
    "    for row in range(len(n)):\n",
    "        # and for every value between 0 and v\n",
    "        for value in range(v):\n",
    "            denom = n[row]\n",
    "            # If the coin denom equals the value, we can make change\n",
    "            if value+1 == denom:\n",
    "                table[row][value] = True\n",
    "            # If we can make change for (value - denom) with previous denoms, \n",
    "            # we can make change.\n",
    "            elif value-denom >= 0 and table[row-1][value-denom] == True:\n",
    "                table[row][value] = True\n",
    "            # If we can make change for value with previous denoms, we can make change.\n",
    "            elif row > 0:\n",
    "                if table[row - 1][value] == True:\n",
    "                    table[row][value] = True\n",
    "            # Otherwise we can't make change for value using denoms n_1, ... , n_row\n",
    "            else:\n",
    "                table[row][value] = False\n",
    "                \n",
    "    print(table)\n",
    "\n",
    "    # The solution is the final table entry, representing whether \n",
    "    # we can make change for v using all available denominations\n",
    "    solution = bool(table[-1][-1])\n",
    "    print(\"Q. Can we make change for %d with denominations %s?\" % (v, n))\n",
    "    print(\"A. %s\" % solution)\n",
    "    return solution\n",
    "\n",
    "\n",
    "v = 30\n",
    "n = [1, 5, 10, 10, 10, 25]\n",
    "coin_change_no_repeat(v=v, n=n)\n",
    "\n",
    "v = 30\n",
    "n = [25, 10, 5, 10, 10, 1]\n",
    "coin_change_no_repeat(v=v, n=n)\n",
    "\n",
    "# Test from DPV\n",
    "n = [1, 5, 10, 20]\n",
    "for v in (16, 31, 40):\n",
    "    coin_change_no_repeat(v=v, n=n)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4: Analyze runtime complexity ###\n",
    "\n",
    "We loop over every value between $1$ and $v$ and we do this $n$ times. All our other operations are $O(1)$. The runtime complexity is:\n",
    "\n",
    "$$O(nv)$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.6",
   "language": "python",
   "name": "python_3.6"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}