DP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Subset-Sum Problem (SSP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **Subset Sum problem (SSP)** is defined as follows:\n",
    "\n",
    ">Given a set $S = \\{x_1, x_2, \\ldots, x_n\\}$ of positive integers,\n",
    ">and a positive integers $t$, is there a subset of $S$ whose sum is equal to $t$?\n",
    "\n",
    "This is the **decision version** of SSP as it only asks for a true/false answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Example\n",
    "\n",
    "$S=\\{1,2,3,10\\}$ and $t=13$.\n",
    "\n",
    "A solution is given by $\\{1,2,10\\}$. There is also another solution: $\\{3,10\\}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exhaustive search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An **exhaustive search algorithm** for this problem can written *iteratively* as follows:\n",
    "\n",
    "**INPUT:** A set $S = \\{x_1, x_2, \\ldots, x_n\\}$ of positive integers, and a positive integer $t$.\n",
    "\n",
    "**OUTPUT:** $(c_1,\\ldots,c_n)$ such that $\\sum_{i=1}^n c_i x_i = t$\n",
    "\n",
    "1. **for all** $(c_1,\\ldots,c_n)\\in\\{0,1\\}^n$ **do**\n",
    "2. $\\quad$ **if** $\\sum_{i=1}^n c_i x_i = t$ **then**\n",
    "3. $\\qquad$ **return** $(c_1,\\ldots,c_n)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now think of the exhaustive search as a binary tree, where at each level we decide whether to include the $i^\\text{th}$ number or not. For example, if $S = \\{a, b, c, d\\}$ then we get:\n",
    "\n",
    "![](img/ssp-binary-tree.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a recursive version of the exhaustive search algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "......................................................................................\n",
    "......................................................................................\n",
    "......................................................................................\n",
    "......................................................................................\n",
    "......................................................................................\n",
    "......................................................................................\n",
    "......................................................................................\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dynamic Programming."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above iterative pseudocode considers the subsets of $S$ as the search space.\n",
    "Another way to search for solutions is to iteratively build the answer for smaller target values $t' = 0, 1, 2, 3, \\ldots$ until we reach $t$.\n",
    "\n",
    "If we have built all the possible sums from the subset $\\{x_1,\\ldots,x_k\\}$, what other sums become possible if we add $x_{k+1}$ to the set?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "............................................................................\n",
    "............................................................................\n",
    "............................................................................\n",
    "............................................................................\n",
    "............................................................................\n",
    "............................................................................\n",
    "............................................................................\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now explain how we can use this for a bottom-up approach to decide SSP."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint, sample"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_S_t(n, MAX_X = 100):\n",
    "    S = [randint(1,MAX_X) for i in range(n)]\n",
    "    t = sum(sample(S,randint(1,n)))\n",
    "    return S,t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([42, 26, 59, 27, 18, 74, 92, 54, 85, 31], 96)"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_S_t(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1) Memoization (Top-down approach)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.266563Z",
     "start_time": "2022-10-25T11:38:11.256547Z"
    }
   },
   "outputs": [],
   "source": [
    "# Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.281559Z",
     "start_time": "2022-10-25T11:38:11.271567Z"
    }
   },
   "outputs": [],
   "source": [
    "# Test examples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Bottom-up approach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.295714Z",
     "start_time": "2022-10-25T11:38:11.286560Z"
    }
   },
   "outputs": [],
   "source": [
    "# Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.311861Z",
     "start_time": "2022-10-25T11:38:11.295714Z"
    }
   },
   "outputs": [],
   "source": [
    "# Test examples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List of references\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "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.11.1"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "vscode": {
   "interpreter": {
    "hash": "6d1e45cadc3597bb8b6600530fbdf8c3eefe919a24ef54d9d32b318795b772e0"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}