{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Knapsack problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have to fill a knapsack to go hiking on the mountain. You have a small knapsack with a limited capacity, let's say 10. You can imagine this capacity in liters of a very small backpack. You have some items to put inside and obviously they exceed the capacity of yoyur knapsack. For example, you have four items with size 4, 6, 3 and 3. These items are differently useful, let's say their utilities are 8, 7, 5 and 4. We would like to maximize the utility inside the knapsack without exceeding the capacity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Clearly using a knapsack is just for simplification. The same problem can be applied to a wide variety of situations:\n",
    "- images on a web page (each one has a utility and a size, you cannot put too many)\n",
    "- information delivered to your customers (each piece of information has a utility and tires the customer which has a limited patience)\n",
    "- the timing of your work activities (each one has an impact and a time and, obviously, you have a limited time)\n",
    "- resource allocation\n",
    "- navigation system, where pieces of road are the items, utility is your time which you want to minimize and the size constraint becomes instead the constraint that you must reach your destination.\n",
    "\n",
    "and tons of other situations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Whenever you approach a problem, the very first thing you should think about is how to organize your data, at least the data in input and your solution. In this case for sure we need:\n",
    "- INPUT: a list with the names of the items, in our example N=[\"water\",\"blanket\",\"food\",\"binocular\"]\n",
    "- INPUT: a list of the size S=[3,6,4,3]\n",
    "- INPUT: a list of the utilities U=[5,7,8,4]\n",
    "- OUTPUT: a list of bool which states whether the item is in the knapsack or not. For example if we put inside only water and food it is <font color=GREEN>Status=[True,False,True,False]</font>\n",
    "\n",
    "Clearly the lists must be absolutely kept synchronized in case they are modified."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Brute-force"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem can be solved obviously using brute-force, trying all the possibile combinations of items. This requires $2^N$ attempts, where $N$ is the number of items. Each attempt requires you to multiply the make a scalar multiplication of the list of bool with the size ($N$ multiplications) and with the utilities ($N$ multiplications). This is $2N$ multiplications. So a total of $2^N\\cdot 2N$ multiplications, a number which becomes huge when $N$ grows. For example, for N=10 it is 20000, for N=20 it is 42 millions, for N=30 it is 64 billions.\n",
    "\n",
    "This is the complexity in the worst case, but it is also the complexity if you find the solution at the first attempt, since you need anyway to try all the possible combinations to be sure to have the best one. It would be nice if we could cut some combinations which are obviouly impossible (over capacity) or evidently worse (less utility). This is particularly true if we have a lot of items and you can exclude a lot of them with a single decision."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorting the items"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is useful for the next algorithm to have the items sorted in order of utility, from the most useful one to the less useful one. You can use any sorting algorithm you like, but you have to modify it because everything you do to the list U must be done also on the list S and N, as they must be kept synchronized."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N=[\"water\",\"blanket\",\"food\",\"binocular\"]\n",
    "S=[3,6,4,3]\n",
    "U=[5,7,8,4]\n",
    "\n",
    "def bubbleSort(U,S,N):\n",
    "# your code here. You do not need to use bubbleSort, you can use any other sorting algorithm you want\n",
    "    \n",
    "    return U,S,N\n",
    "\n",
    "print bubbleSort(U,S,N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The result of the example should be:\n",
    "- N=[\"food\",\"blanket\",\"water\",\"binocular\"]\n",
    "- S=[4,6,3,3]\n",
    "- U=[8,7,5,4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Branch and bound"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Branch and bound is a heuristic technique for maximisation problems which does not improve the worst case complexity but only the average case. Its strategy is to branch the problem into sub problems, each with a bound on the maximisation function, and exploring the sub problem which is more promising. This sub problem is then branched again into sub sub problems, each with a bound, and so on until we may not go on anymore and a solution is found. If the solution’s utility is largest than the bound on every open sub problem, then it is also the maximum; otherwise the appropriate branches are examined until a better solution is found or until no branch with a bound higher than the current best solution exists."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, consider a knapsack problem with a maximum size of 10, four items of sizes 4, 6, 3, 3 and utilities 8, 7, 5, 4. We can immediately put a bound on the utility function which clearly may never be larger than 24, the sum of the utilities of all the items, while the effective utility for the moment is 0 and the size is 0 (see yellow box). \n",
    "\n",
    "Then, starting from the item with the largest utility, called item A with utility 8 and size 4, we branch into the two sub problem A1 “item A is included” and A0 “item A is excluded”. The bound on these two sub problems is now 24 for the first and 16 for the second, while the effective values are 8 and 0 for the utilities and 4 and 0 for the sizes (see the two pink boxes). \n",
    "\n",
    "We go on with the first and most promising branch and consider now item B with utility 7 and size 6. We branch into A1-D1 with bound on utility of 24, an effective utility of 15 and size of 10 and A1-D0 with a bound of 17, an effective utility of 8 and a size of 5. If we go on with the more promising branch adding item B with a utility of 4 and a size of 4 (see the two green boxes). \n",
    "\n",
    "Choosing again the most promising branch, A1-B1, we discover that there is no possibility A1-B1-C1 since the effective size becomes 13 which exceeds the maximum of 10. Therefore this branch is cancelled and from here the only possibility is A1-B1-C0 which has a bound on utility equal to 19 and an effective utility of 15 and size of 10 (see the two left blue boxes). \n",
    "\n",
    "Choosing between branch A1-B1-C0, A1-B0 and A0 we take the first and branch it into the impossible solution A1-B1-C0-D1 which exceeds the allowed size and the solution A1-B1-C0-D0 with a size of 10 and a utility of 15 (see the two right red circles). This is a possible solution, however we are not sure that it is the best one because there are still unexplored branches with a bound larger than 15. \n",
    "\n",
    "We therefore explore the most promising one, which is A1-B0 (the left green box). We branch it into A1-B0-C1 with a bound of 17 and A1-B0-C0 with a bound of 12 (the two right blue boxes). \n",
    "\n",
    "We go on with the most promising one which is A1-B0-C1 and branch it into the two possible solutions A1-B0-C1-D1 with a utility of 17 and a size of 10 and A1-B0-C1-D0 with a utility of 13 and a size of 7 (the two right red circles). \n",
    "\n",
    "The best solution found until now is A1-B0-C1-D1 whose utility of 17 is larger than every unexplored branch, which are A0 with bound 16 and A1-B0-C0 with bound 12, and therefore this is the best solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"http://www.paolocoletti.it/algorithmicthinking/images/knapsack.jpg\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using this algorithm we saved the calculations for exploring the branch A1-B1-C1 because it is impossible and the branches A0 and A1-B0-C0 because they are sub-optimal."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Data structures for the algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have already seen the data structures for the input and output information of the problem. Let's see now how to store the data that we build during the algorithm's execution. \n",
    "\n",
    "As we can see from the picture, we need to store for each open branch the maximum utility, the utility, the size and a list of bool which indicates which items have been included and which have been excluded.\n",
    "\n",
    "We thus keep a list of data called BB where each element is a list such as, for the fourth blue rectangle: [12,8,4,[True,False,False]].\n",
    "\n",
    "Every time we branch, we remove the element which is branched and we insert in the list the two or one valid elements created. We always try to keep the list in order of maximum utility. In the previous example, the list starts evolves as follow (please, follow the picture above and try to build it up yourself instead of reading it!!!):\n",
    "<p>[ [24,0,0,[]] ]\n",
    "<p>[ [24,8,4,[True]] , [16,0,0,[False]] ]\n",
    "<p>[ [24,15,10,[True,True]] , [17,8,4,[True,False]] , [16,0,0,[False]] ]\n",
    "<p>[ [19,15,10,[True,True,False]] , [17,8,4,[True,False]] , [16,0,0,[False]] ]\n",
    "<p>[ [17,8,4,[True,False]] , [16,0,0,[False]] , [15,15,10,[True,True,False,False]] ]\n",
    "<p>[ [17,13,7,[True,False,True]] , [16,0,0,[False]] , [15,15,10,[True,True,False,False]] , [12,8,4,[True,False,False]] ]\n",
    "<p>[ [17,17,9,[True,False,True,True]] , [16,0,0,[False]] , [15,15,10,[True,True,False,False]] , [13,13,7,[True,False,True,False]] , [12,8,4,[True,False,False]] ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When do we finish? Think about it!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We finish when in the first place of the list there is an element which is a **leaf**, i.e. a terminal element which cannot be branched anymore. We easily spot these elements because the size of the bool list is equal to the number of items you have (for each item you have decided whether including or not it in the knapsack)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import copy\n",
    "\n",
    "def bubbleSort(U,S,N):\n",
    "\n",
    "    # copy here your sorting function that you have written above, just to be sure\n",
    "\n",
    "\n",
    "def calcUtil(U,Status):\n",
    "    # this function calculates the utility scalar-multiplying the utility list with the bool list \n",
    "    # (this means U[0]*Status[0]+U[1]*Status[1]+...+U[N]*Status[N])\n",
    "    # PAY ATTENTION that Status is shorter (it contains the items decided so far and not the other items), \n",
    "    # you will have to skip the rest of U\n",
    "\n",
    "    # write your code here\n",
    "    \n",
    "    \n",
    "    \n",
    "def calcMaxUtil(U,Status):\n",
    "    # this function calculates the maximum utility exactly as the previous function but once Status is over you have to...\n",
    "\n",
    "    # write your code here\n",
    "    \n",
    "    \n",
    "def calcSize(S,Status):\n",
    "    # do you really need this function or haven't you perhaps already written it?\n",
    "\n",
    "    # take your decisions and write or not write your code here (in the latter case, remove also the def calcSize)\n",
    "    \n",
    "    \n",
    "def insertBB(BB,maxutility,utility,size,Status):\n",
    "    # this function inserts [maxutility,utility,size,Status] into the data structure BB in its right place, \n",
    "    # keeping BB sorted from largest maxutility to smallest\n",
    "    i=0\n",
    "    print(\"Insert [\",maxutility,utility,size,Status, \"] into\",BB, end=\" \") \n",
    "    while i<len(BB):\n",
    "        if BB[i][0]<maxutility: # let's see whether we find a space for our maxutility\n",
    "            BB.insert(i,[maxutility,utility,size,Status])\n",
    "            print(\" and getting\", BB,\"\\n\")\n",
    "            return # I return just to interrupt the function, there is nothing to return here\n",
    "        i=i+1\n",
    "    # if we arrive here we have not yet inserted it, so it goes at the end\n",
    "    BB.append([maxutility,utility,size,Status])\n",
    "    print(\"and getting \", BB,\"\\n\")\n",
    "    \n",
    "# I have already written this function for you to avoid that you spend too much time.\n",
    "# thre function also prints some debugging information\n",
    "    \n",
    "    \n",
    "# here the program starts, let's set up the situation of the example \n",
    "# (to apply it to another example you have just to modify these values)\n",
    "N=[\"water\",\"blanket\",\"food\",\"binocular\"]\n",
    "S=[3,6,4,3]\n",
    "U=[5,7,8,4]\n",
    "maxSize=10\n",
    "\n",
    "# we sort the data by utility\n",
    "# please do it\n",
    "\n",
    "# we set up the first branch, i.e. the ROOT\n",
    "# please do it, look at the picture for how is the root of the tree\n",
    "\n",
    "# we put the first branch in the BB list\n",
    "# easy peasy, you have a function which does it!\n",
    "\n",
    "# now we loop and write the core of the algorithm\n",
    "while True:\n",
    "    # we take the first element out from the list and store it in a variable. Do not forget that the element is made up of \n",
    "    # [maxutility,utility,size,Status]\n",
    "    # please write the code here\n",
    "    \n",
    "    # we check whether the element we just took out is a leaf, i.e. Status has exactly length equal to the number of items. \n",
    "    # In this case, it is finished and we print the result.\n",
    "    # it would be nice to print the result in a human-readable form, such as:\n",
    "    # take food\n",
    "    # leave blanket\n",
    "    # take water\n",
    "    # take binocular\n",
    "    \n",
    "    # please write the code here\n",
    "\n",
    "    \n",
    "    # else when the first element of BB is not a leaf, we have to branch \n",
    "    # building both branches and inserting them in the data structure BB (if they do not exceed the size)\n",
    "\n",
    "    # branch left, we consider the next item and we DO take it. We have to update utility and size, maxutility remains the same\n",
    "    # this might have a consequence that we exceed the size and in this case we do NOT insert it in the BB structure\n",
    "\n",
    "    # NOTE: if for any reason you need to copy a list, beware that a=b is not a duplication of the list but only of the pointer\n",
    "    # to copy a list duplicating it, use  a=copy.deepcopy(b)  In this way a and b will be two different objects using two different spaces in the memory\n",
    "    \n",
    "    # please write the code here\n",
    "    \n",
    "    \n",
    "    \n",
    "    # branch right, we consider the next item and we DO NOT take it. We have to update maxutility, while utility and size remain the same\n",
    "    # there is no risk  that the size is exceeded\n",
    "\n",
    "    # please write the code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Another exercise"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the same code with another snapsack with 10 items with various utilities and sizes and a larger capacity, which does not have a trivial solutions (i.e. a solution which takes all the items or which takes simply the items with the largest utilities)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
