Dynamic_Programming_Part_2_knapsack_and_panlidorm.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"\\nProblem Defination: Given a sequence of chars, get the longest panlindorm it contains.\\n\\ne.g \\nInput: 'ABA'\\nOutput: 'ABA'\\nInput: 'ABAAAAB'\\nOutput: 'BAAAAB'\\nInput: 'I Live on the time, emit no evil at all.'\\nOutput: 'Live on the time, emit no evil'\\n\""
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "Problem Defination: Given a sequence of chars, get the longest panlindorm it contains.\n",
    "\n",
    "e.g \n",
    "Input: 'ABA'\n",
    "Output: 'ABA'\n",
    "Input: 'ABAAAAB'\n",
    "Output: 'BAAAAB'\n",
    "Input: 'I Live on the time, emit no evil at all.'\n",
    "Output: 'Live on the time, emit no evil'\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "letters_digits = string.ascii_letters + string.digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "string.ascii_letters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "from icecream import ic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_panlindorm(string):\n",
    "    string = ''.join([c for c in string if c in letters_digits]).upper()\n",
    "    return string == string[::-1]\n",
    "\n",
    "def get_prefix_panlindorm(string):\n",
    "    candidates = [string[:i] for i in range(len(string)+1) if is_panlindorm(string[:i])]\n",
    "    return max(candidates, key=len)\n",
    "\n",
    "@lru_cache(maxsize=2*10)\n",
    "def get_panlindorm(string):\n",
    "    if len(string) == 1: return string\n",
    "    return max([get_prefix_panlindorm(string), get_panlindorm(string[1:])], key=len).strip()\n",
    "\n",
    "assert is_panlindorm('ABA')\n",
    "assert is_panlindorm('ABBBA')\n",
    "assert is_panlindorm('BBBB')\n",
    "assert not is_panlindorm('ABAA')\n",
    "assert is_panlindorm('Live on time, emit no evil')\n",
    "\n",
    "assert get_prefix_panlindorm('ABA')  == 'ABA'\n",
    "assert get_prefix_panlindorm('ABABBBB') == 'ABA'\n",
    "assert get_prefix_panlindorm('ABCDEEEEEE') == 'A'\n",
    "\n",
    "assert get_panlindorm('ABA') == 'ABA'\n",
    "assert get_panlindorm('ABAAAAAA') == 'AAAAAA'\n",
    "assert get_panlindorm('I live on time, emit no evil at all') == 'live on time, emit no evil'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Knapsack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "items_random = [(random.randint(1, 10), random.randint(1, 20)) for _ in range(20)]\n",
    "weights = [i[0] for i in items_random]\n",
    "values = [i[1] for i in items_random]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 331,
   "metadata": {},
   "outputs": [],
   "source": [
    "K = 50"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "from icecream import ic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 334,
   "metadata": {},
   "outputs": [],
   "source": [
    "#solution = [0] * len(items_random)\n",
    "solution = [[0] * len(items_random) for _ in range(K)]\n",
    "@lru_cache(maxsize=2*10)\n",
    "def knapsack(n, k):\n",
    "    # n is the index of the last one candidates\n",
    "    if n < 0: return 0\n",
    "    if weights[n] > k:  return knapsack(n-1, k)\n",
    "    \n",
    "    exclude = knapsack(n-1, k)\n",
    "    include = values[n] + knapsack(n - 1, k - weights[n])\n",
    "\n",
    "    if include > exclude:\n",
    "        solution[k][n] = 1\n",
    "        return include\n",
    "    else:\n",
    "        solution[k][n] = 0\n",
    "        return exclude"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 247,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsack(len(items_random)-1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 335,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "91"
      ]
     },
     "execution_count": 335,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsack(len(items_random)-1, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(3, 10),\n",
       " (9, 20),\n",
       " (5, 7),\n",
       " (3, 9),\n",
       " (1, 20),\n",
       " (7, 10),\n",
       " (9, 8),\n",
       " (3, 4),\n",
       " (5, 15),\n",
       " (7, 8),\n",
       " (10, 14),\n",
       " (7, 5),\n",
       " (10, 13),\n",
       " (3, 10),\n",
       " (6, 8),\n",
       " (1, 19),\n",
       " (10, 1),\n",
       " (6, 17),\n",
       " (7, 8),\n",
       " (7, 7)]"
      ]
     },
     "execution_count": 206,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "items_random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]"
      ]
     },
     "execution_count": 210,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution[5][15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights[15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 125,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution[5 - 1][10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于任意的solution单元，例如 solution[i][j]， 其表示的是，当constraint时i的时候，最大的候选集是j的时候，j 选不选。 那么，如果j是1，就是 $item_j$被选择了，反之，没有被选择。 那么该如何判断选择了哪一个呢？ \n",
    "\n",
    "因为我们的递归过程是\n",
    "```\n",
    "exclude = knapsack(n-1, k)\n",
    "include = values[n] + knapsack(n - 1, k - weights[n])\n",
    "\n",
    "return max(exclude, include)\n",
    "```\n",
    "即，一直思考的是最后一个元素需不需要加进来，如果需要，就加上，如果加不进来，就不加。 所以，如果当前的solution[i][j]是0， 表示没有被选择，那么被选择的元素就是 soluion[i][j]， j 一直减小，遇到的第一个是 1 的元素。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例如，对于 solution[4][19]是0，一路往前“推进”，第一个不是0的是15， 就是说，第15个item，是被选入的。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当我们获得了一个解，那么我们的问题是，怎么获得接下来的解呢？ \n",
    "我们观察一下递归调用的过程： \n",
    "```\n",
    "values[n] + knapsack(n - 1, k - weights[n])\n",
    "```\n",
    "\n",
    "就是说  **n** 有没有被选中，程序是依靠 **n-1**和 constraint 是 k - weights[n]确定的。 所以，当我们知道 constraint 是 **k**， **n**有没有被选择的时候，我们可以继续通过 **n-1**和 **k-weights[n]** 得知在 **n**和 **k**的时候，系统算出来的第2个答案。 然后以此类推。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以，我们先定义一个函数，这个函数可以输入一个候选的item的最大序号n， 目前的constraint, 输出是这个情况下，系统选择的第1个item. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],\n",
       " [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],\n",
       " [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]]"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [],
   "source": [
    "# it's a utility function\n",
    "def first(iterables, predicate):\n",
    "    iterables = iter(iterables)\n",
    "    for i in iterables:\n",
    "        if predicate(i): return i\n",
    "    return None\n",
    "\n",
    "def get_chosen_item(constraint, candidate_size, solve):\n",
    "    index = first(enumerate(solve[constraint][:candidate_size][::-1]), predicate=lambda x: x[1] == 1)\n",
    "    if index:\n",
    "        return (candidate_size - 1) - index[0] \n",
    "    else:\n",
    "        return None\n",
    "    # when candidate_size set to 20, and the index is 0, means the last one is chosen, which index is 19\n",
    "    # when candidate_size is 1, and the index is 0, means the item index 0, is selected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 328,
   "metadata": {},
   "outputs": [],
   "source": [
    "get_chosen_item(constraint=4, candidate_size=20, solve=solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "例如， 这个函数告诉我们，当 constraint是4，candidate_size是19的时候，16是必须要选择的。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights[15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "19"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "values[15]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们在这个基础（constraint == 4, candidate_size=19）之上，继续获得 `knapsack(n - 1, k - weights[n])` 的解， 此时， 为了方便起见，因为我们已经知道了第一个被选择的是index == 15的item， 所以我们可以把candiadte_size 设置为 15, constraint == 4 - 1 (1是weights[15]的值), 那么我们能够继续获得下一个被选择的item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 173,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_chosen_item(constraint=3, candidate_size=15, solve=solution)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于此，我们递归获得完整的解决方案："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 366,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_complete_solution(solver, constraint, candidate_size=None):\n",
    "    candidate_size = candidate_size or len(solver[0])\n",
    "    index = get_chosen_item(constraint, candidate_size, solver)\n",
    "    if index: \n",
    "        print('Get Item[{}], weight == {}, value == {}'.format(index, weights[index], values[index]))\n",
    "        get_complete_solution(solver, constraint - weights[index], index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
       " [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]"
      ]
     },
     "execution_count": 223,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Get Item[4], weight == 1, value == 20\n"
     ]
    }
   ],
   "source": [
    "get_complete_solution(solution, constraint=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 367,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Get Item[15], weight == 1, value == 19\n",
      "Get Item[4], weight == 1, value == 20\n"
     ]
    }
   ],
   "source": [
    "get_complete_solution(solution, constraint=4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 389,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Get Item[17], weight == 6, value == 17\n",
      "Get Item[15], weight == 1, value == 19\n",
      "Get Item[13], weight == 3, value == 10\n",
      "Get Item[8], weight == 5, value == 15\n",
      "Get Item[4], weight == 1, value == 20\n"
     ]
    }
   ],
   "source": [
    "get_complete_solution(solution, constraint=19)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 390,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "91"
      ]
     },
     "execution_count": 390,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsack(k=19, n=len(items_random)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## We Could Merge these together!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "metadata": {},
   "outputs": [],
   "source": [
    "#solution = [0] * len(items_random)\n",
    "# refactor it to with soltion in argument\n",
    "\n",
    "@lru_cache(maxsize=2*10)\n",
    "def knapsack(n, k, solution):\n",
    "    # n is the index of the last one candidates\n",
    "    if n < 0: return 0\n",
    "    if weights[n] > k:  return knapsack(n-1, k, solution)\n",
    "    \n",
    "    exclude = knapsack(n-1, k, solution)\n",
    "    include = values[n] + knapsack(n - 1, k - weights[n], solution)\n",
    "\n",
    "    if include > exclude:\n",
    "        solution[k][n] = 1\n",
    "        print(k, n)\n",
    "        return include\n",
    "    else:\n",
    "        solution[k][n] = 0\n",
    "        return exclude"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 249,
   "metadata": {},
   "outputs": [],
   "source": [
    "def knapsack_with_solution(items, constraint):\n",
    "    weights = [w for w, v in items]\n",
    "    values = [v for w, v in items]\n",
    "    \n",
    "    solution = [[0] * len(items) for _ in range(constraint+1)]\n",
    "    \n",
    "    optimal_result = knapsack(k=constraint, n=len(items)-1, solution=solution)\n",
    "    print('Optimal Value Sum is : {}'.format(optimal_result))\n",
    "    print(solution)\n",
    "    get_complete_solution(solution, constraint=constraint)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 250,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unhashable type: 'list'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-250-7690b13461ab>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mknapsack_with_solution\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mitems_random\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-249-9e077590cc70>\u001b[0m in \u001b[0;36mknapsack_with_solution\u001b[0;34m(items, constraint)\u001b[0m\n\u001b[1;32m      5\u001b[0m     \u001b[0msolution\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0m_\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mconstraint\u001b[0m\u001b[0;34m+\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m     \u001b[0moptimal_result\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mknapsack\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mconstraint\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mn\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mitems\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msolution\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0msolution\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Optimal Value Sum is : {}'\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0moptimal_result\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      9\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msolution\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mTypeError\u001b[0m: unhashable type: 'list'"
     ]
    }
   ],
   "source": [
    "knapsack_with_solution(items_random, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "metadata": {},
   "outputs": [],
   "source": [
    "# in order to let 'solution', the list type saved to cache, we need add an utility function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 279,
   "metadata": {},
   "outputs": [],
   "source": [
    "def to_list(tuple_data):\n",
    "    return [to_list(t) if isinstance(t, tuple) else t for t in tuple_data]\n",
    "\n",
    "def to_tuple(list_data):\n",
    "    return tuple(to_tuple(t) if isinstance(t, list) else t for t in list_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 288,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import wraps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 310,
   "metadata": {},
   "outputs": [],
   "source": [
    "def memo(func):\n",
    "    cache = {}\n",
    "    @wraps(func)\n",
    "    def _wrap(*args, **kwargs):\n",
    "        args = list(args)\n",
    "        \n",
    "        for ii, a in enumerate(args): \n",
    "            if isinstance(a, list): args[ii] = to_tuple(a)\n",
    "        \n",
    "        for k, v in kwargs.items():\n",
    "            if isinstance(v, list): kwargs[k] = to_tuple(v)\n",
    "                \n",
    "        union_key = str(args) + str(kwargs)\n",
    "        \n",
    "        if union_key in cache: return cache[union_key]\n",
    "        else:\n",
    "            result = func(*args, **kwargs)\n",
    "            cache[union_key] = result\n",
    "            return result   \n",
    "    return _wrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 311,
   "metadata": {},
   "outputs": [],
   "source": [
    "def some_func_with_list(argument):\n",
    "    print('called')\n",
    "    return sum(argument)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 312,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n",
      "called\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    v = some_func_with_list([1, 2, 3])\n",
    "    print(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 313,
   "metadata": {},
   "outputs": [],
   "source": [
    "# called 6 times!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 314,
   "metadata": {},
   "outputs": [],
   "source": [
    "@memo\n",
    "def some_func_with_list(argument):\n",
    "    print('called')\n",
    "    return sum(argument)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 315,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "called\n",
      "6\n",
      "6\n",
      "6\n",
      "6\n",
      "6\n",
      "6\n",
      "6\n",
      "6\n",
      "6\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "for i in range(10):\n",
    "    v = some_func_with_list([1, 2, 3])\n",
    "    print(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 319,
   "metadata": {},
   "outputs": [],
   "source": [
    "# called 1 time, but print value 10 times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 307,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 307,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# e.g \n",
    "to_list((1, 2, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 276,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, [1, 2, 3, [1, 2, 3]]]"
      ]
     },
     "execution_count": 276,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# e.g \n",
    "to_list((1, 2, 3, (1, 2, 3, (1, 2, 3))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 2, 3)"
      ]
     },
     "execution_count": 280,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# e.g \n",
    "to_tuple([1, 2, 3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((1, 2, 3), (4, 5, 5))"
      ]
     },
     "execution_count": 281,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# e.g\n",
    "to_tuple([[1, 2, 3], [4, 5, 5]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 320,
   "metadata": {},
   "outputs": [],
   "source": [
    "#solution = [0] * len(items_random)\n",
    "# refactor it to with soltion in argument\n",
    "\n",
    "@memo\n",
    "def knapsack(n, k, solution):\n",
    "    # n is the index of the last one candidates\n",
    "    if n < 0: return 0\n",
    "    if weights[n] > k:  return knapsack(n-1, k, solution)\n",
    "    \n",
    "    exclude = knapsack(n-1, k, solution)\n",
    "    include = values[n] + knapsack(n - 1, k - weights[n], solution)\n",
    "\n",
    "    if include > exclude:\n",
    "        solution[k][n] = 1\n",
    "        print(k, n)\n",
    "        return include\n",
    "    else:\n",
    "        solution[k][n] = 0\n",
    "        return exclude"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Optimizatoin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dynamic Programming Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Optimization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraint Optimization Programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Max Intergral Optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(7, 16),\n",
       " (2, 14),\n",
       " (2, 6),\n",
       " (2, 5),\n",
       " (3, 16),\n",
       " (2, 17),\n",
       " (4, 6),\n",
       " (7, 5),\n",
       " (10, 8),\n",
       " (1, 13),\n",
       " (3, 10),\n",
       " (10, 12),\n",
       " (3, 19),\n",
       " (7, 12),\n",
       " (5, 4),\n",
       " (8, 14),\n",
       " (10, 12),\n",
       " (4, 10),\n",
       " (2, 20),\n",
       " (3, 15)]"
      ]
     },
     "execution_count": 217,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "items_random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]"
      ]
     },
     "execution_count": 222,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kk"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "33"
      ]
     },
     "execution_count": 221,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(7, 16),\n",
       " (2, 14),\n",
       " (2, 6),\n",
       " (2, 5),\n",
       " (3, 16),\n",
       " (2, 17),\n",
       " (4, 6),\n",
       " (7, 5),\n",
       " (10, 8),\n",
       " (1, 13),\n",
       " (3, 10),\n",
       " (10, 12),\n",
       " (3, 19),\n",
       " (7, 12),\n",
       " (5, 4),\n",
       " (8, 14),\n",
       " (10, 12),\n",
       " (4, 10),\n",
       " (2, 20),\n",
       " (3, 15)]"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "items_random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 2, 2, 2, 3, 2, 4, 7, 10, 1, 3, 10, 3, 7, 5, 8, 10, 4, 2, 3]"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[16, 14, 6, 5, 16, 17, 6, 5, 8, 13, 10, 12, 19, 12, 4, 14, 12, 10, 20, 15]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(weights)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knapsack(19, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CV \n",
    "+ 可以参考 Stanford NLP, CV Group \n",
    "+ 素雅 \n",
    "+ 突出重点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 面试 \n",
    "+ 突出自己的优点, e.g 学习能力 我的抗压能力\n",
    "+ 引导面试官\n",
    "+ 优秀的面试官发你的潜力 发现的你长处 看看你这个长处到底有多长\n",
    "+ 糟糕的面试官是，只关注你会不会他想让你知道的那个东西，关注你的“经历”"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 快速入行 技能驱动 \n",
    "## 不管你在哪个公司 只要面对的问题大体类似 "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}