{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "*This notebook is an exploration of the 0-1 knapsack problem as formulated by lecture 1 and 2 of MIT's 6.00.2x course.*\n", "\n", "
\n", "\n", "# The 0/1 Knapsack Problem\n", "\n", "The 0/1 Knapsack problem occurs whenever you want to maximize some value by selecting an optimal subset of items while obeying certain constraints. For example, a robber trying to figure out which items to steal; he can't take everything (too heavy) so he wants to maximize the amount of value he can take. Another formulation has an individual on a calorie-restricting diet; she wants to maximize the enjoyment from the food she eats while still staying beneath some set calorie limit.\n", "\n", "As an aside, it's called the \"0/1\" knapsack problem because it is discrete; the robber either takes an item or does not, food is either consumed or left untouched. The \"continuous\" knapsack problem is significantly easier to solve as you can just take as much as possible right up to the limit; for example, if the robber comes across a store of gold dust then he can just fill his bag as high as it can go.\n", "\n", "## Diet Scenario\n", "\n", "I will look at the diet scenario as it is the one covered by the course.\n", "\n", "> Dave is on a calorie-restricting diet that limits him to 750 calories per meal. He arrives at a restaurant and is trying to decide what to order. He assigns pleasure values to each food and makes note of their cost (in calories).\n", "\n", "**Simplification**: each item on the menu can only be ordered once.\n", "\n", "### Data\n", "\n", "Provided by the course.\n", "\n", "I'm going to try out [pandas](http://pandas.pydata.org/) for this." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import pandas as pd" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Read data from csv file\n", "data = pd.read_csv(\"food-value-calories.csv\")" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
FoodValueCalories
0wine89123
1beer90154
2pizza95258
3burger100354
4fries90365
5cola79150
6apple5095
7donut10195
\n", "
" ], "text/plain": [ " Food Value Calories\n", "0 wine 89 123\n", "1 beer 90 154\n", "2 pizza 95 258\n", "3 burger 100 354\n", "4 fries 90 365\n", "5 cola 79 150\n", "6 apple 50 95\n", "7 donut 10 195" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Display the data \n", "# head() displays a default 5 elements. To view all, pass the total number of elements (is there a better way?)\n", "data.head(len(data))" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
ValueCalories
count8.0000008.000000
mean75.375000211.750000
std30.556447103.368619
min10.00000095.000000
25%71.750000143.250000
50%89.500000174.500000
75%91.250000282.000000
max100.000000365.000000
\n", "
" ], "text/plain": [ " Value Calories\n", "count 8.000000 8.000000\n", "mean 75.375000 211.750000\n", "std 30.556447 103.368619\n", "min 10.000000 95.000000\n", "25% 71.750000 143.250000\n", "50% 89.500000 174.500000\n", "75% 91.250000 282.000000\n", "max 100.000000 365.000000" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Compute some descriptive statistics\n", "data.describe()" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Plot (because why not)\n", "%matplotlib inline\n", "import matplotlib.pyplot as plt\n", "# Set style\n", "import matplotlib\n", "matplotlib.style.use('ggplot')" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" }, { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEkCAYAAAAhJPoXAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xtc1HWi//HXDJCKeGEE8khYkZqaulSYSra6Oatd1EUy\n99Sm6dJ2sctvoTq2WdjJeoSmkpZ207bL+bUP8zwCu7h2QjZMaRV3t3I1L3ipUBBhRrwg15nfH/yc\nEws6Iwx8Z76+n49Hj0fzndv7C/Lmy2c+38/X4na73YiIiGlZjQ4gIiLtS0UvImJyKnoREZNT0YuI\nmJyKXkTE5FT0IiImp6IXETE5Fb2IiMmp6EVETE5FLyJicqFGBzjj8OHDfn29qKgoysvL/fqa7UE5\n/Us5/SsYcgZDRmifnH369PHpcTqiFxExORW9iIjJqehFREwuYMboReTC4na7qa6uxuVyYbFYWv06\nR44coaamxo/J2kdrc7rdbqxWK507d27110lFLyKGqK6uJiwsjNDQttVQaGgoISEhfkrVftqSs76+\nnurqarp06dKq52voRkQM4XK52lzyF4rQ0FBcLlern6+iFxFDtGW45kLUlq+Xil5ExOT0d5OIAa5f\nusmnx639zcB2ThI4Gn43uXXPO8v2kDc/Oufzpk6dykMPPcTYsWM9295880327dtHZmZmi8/p378/\ne/fubVVOI+mIXkQuSMnJyaxdu7bJtrVr15KcnGxQovajoheRC9Ktt97Khg0bqK2tBeDHH3/kyJEj\nDBkyhGnTpjFhwgTGjRvHZ5991uy5BQUFzJgxw3N77ty5rF69GoBvv/2W2267jZtuuok777yTI0eO\ndMwOnYOKXkQuSJGRkSQkJPCXv/wFaDyanzRpEp07d2bVqlV89tlnrFmzhmeffRa32+3Ta9bV1fHU\nU0/xxhtvsH79en7961+zYMGC9twNn2iMXkQuWGeGbyZMmMDatWtZvHgxbrebzMxMtmzZgsViobS0\nlKNHjxITE+P19fbt28fu3bv593//d6BxCqkvz2tvKnoRuWBNmDCBZ555hu3bt3P69GmGDRvG6tWr\nqaio4M9//jNhYWGMGDGi2RmtoaGhTY7yz9zvdrsZMGAAH3/8cYfuhzdei762tpZ58+ZRX19PQ0MD\nI0eOZNq0aXzwwQds2LCB7t27A3DHHXdwzTXXAJCdnU1eXh5Wq5VZs2aRkJDQvnshItIKXbt2JSkp\nifT0dM+HsCdOnCAqKoqwsDA2b95McXFxs+fFxsayZ88eampqqK6uZtOmTQwfPpwrrrgCh8PBtm3b\nSExMpK6ujv3793PllVd29K414bXow8LCmDdvHp07d6a+vp6MjAxPcd96661Mntx0SlRxcTEFBQUs\nWbIEp9PJ/PnzWbp0KVarPg6Q9qdpi8HL23TIswkNDaW+vr7V75ucnExqaiqvvvoqACkpKdx9992M\nGzeOYcOG0a9fv2bPiY2NZdKkSdx444307duXIUOGAHDRRRfx+uuvk5GRwfHjx2loaOCee+4J/KK3\nWCx07twZgIaGBhoaGs55hlZhYSFJSUmEhYURExND7969KSoqYsCAAf5LLSLiJzfddBOHDh3y3LbZ\nbGcdevnpHPqnnnqKp556qtljhgwZwocffuj/oG3g0xi9y+Vizpw5lJaWMmHCBPr3788//vEP1q9f\nz8aNG4mPj2fGjBlERETgcDjo37+/57k2mw2Hw9HsNXNzc8nNzQUgMzOTqKgoP+1So9DQUL+/ZntQ\nTmMEy74YnbM9v+9Hjhzx21o3wbJmTltydurUqdXfC5/e1Wq18uKLL3Lq1CkWLVrEDz/8wPjx45k6\ndSoAq1ev5t1332X27Nk+v7Hdbsdut3tu+/sSWxfy5cXaQ7Dk9FWw7IvROdvz+15TU+OXVSfbOnTT\nUdqas6amptn3ol0uJdi1a1euuuoqvv76a3r27InVasVqtTJu3Dj27dsHNB7BV1RUeJ7jcDiw2Wzn\n8zYiIuJHXov++PHjnDp1CmicgfPtt98SGxuL0+n0PGbr1q3ExcUBkJiYSEFBAXV1dZSVlVFSUtLi\nhxkiItIxvA7dOJ1Oli9fjsvlwu12M2rUKK699lpefvllDh48iMViITo6mnvvvReAuLg4Ro0aRXp6\nOlarldTUVM24ERExkNeiv/TSS1m4cGGz7Q8//PBZn5OSkkJKSkrbkomIiF8Ex0fVImJ6v/q/u/z6\ner6cK1FWVsa8efP45ptv6N69O9HR0TzzzDNcccUVLT6+NcsUT548mY8+at05Av6ioheRC5Lb7SY1\nNZXbb7/dc7LUjh07KC8vP2vRn4/6+npCQ0MNL3nQ6pUicoHavHkzYWFhTZYbvuqqq3xaptjtdjN/\n/nxuvPFGxo0b51nXvqCggClTpjBz5kzPBU1+el7Rq6++yi233ILdbmfRokUAVFVVMX36dOx2Ozfe\neGOzNfL9QUf0InJB2r17N0OHDm22vVOnTqxatYpu3brhcDiYNGkS48ePb7IiwLp169ixYweff/45\nDoeDW265hZEjRwKwfft28vLy6Nu3b5PX/eKLLzhw4ACffvopbrebmTNn8te//pWKigp69+7Ne++9\nBzTOdPQ3Fb2IyE/4skzx1q1bSU5OJiQkhOjoaEaOHMk333xDREQECQkJzUoeGos+Pz+f8ePHA41H\n8gcOHOC6667j2Wef5fnnn8dutzNixAi/75OKXkQuSAMGDODTTz9ttv3DDz/0ukzxuYSHh7e43e12\n89BDDzF9+vRm961fv568vDwWLlzI6NGjSUtL831HfKAxehG5II0ePZra2lr+67/+y7Nt586dHDp0\nyOsyxSNGjOCjjz6ioaGBiooKtmzZ4nU59l/84hesXr3acwJqSUkJ5eXllJaW0qVLF2677Tbuv/9+\ntm/f7t8dRUf0IhIgWrt0dGvXkLFYLKxcuZJ58+axYsUKOnXqxCWXXMKjjz7K008/fc5lim+++Wb+\n9re/8ctf/hKLxcLcuXOJiYmhqKjorO83duxYdu3a5VnaPTw83HPi6XPPPYfFYiEsLIwXXnjhvPfF\n6766fb0YYjs7fPiwX18vWBbhUk7/8nUuttHr0QdLzvb8vldVVZ11mON8XCiLmrX09WqXRc1ERCT4\nqOhFRExORS8ihgiQUeOg0Zavl4peRAxhtVqDYmw9ENTX17dpFWDNuhERQ3Tu3Jnq6mpqamrOeR1q\nbzp16nRe89yN0tqcbrcbq9XquXZ3a6joRcQQFouFLl26tPl1gmVGmJE5NXQjImJyKnoREZNT0YuI\nmJyKXkTE5Lx+GFtbW8u8efOor6+noaGBkSNHMm3aNE6ePElWVhZHjx4lOjqatLQ0IiIiAMjOziYv\nLw+r1cqsWbO8LvYjIiLtx2vRh4WFMW/ePDp37kx9fT0ZGRkkJCSwdetWhg4dSnJyMjk5OeTk5HDX\nXXdRXFxMQUEBS5Yswel0Mn/+fJYuXdqmOaAiItJ6XtvXYrF45m82NDTQ0NCAxWKhsLCQMWPGADBm\nzBgKCwsBKCwsJCkpibCwMGJiYujdu/c5V3QTEZH25dM8epfLxZw5cygtLWXChAn079+fyspKIiMj\nAejZsyeVlZUAOByOJtdItNlsOByOZq+Zm5tLbm4uAJmZmURFRbV5Z34qNDTU76/ZHpTTGMGyL0bn\nDIbvezBkBGNz+lT0VquVF198kVOnTrFo0SJ++OGHJvdbLJbzPrPNbrdjt9s9t/19IoFOovCvYMnp\nq2DZF6NzBsP3PRgyQvvkbJdlirt27cpVV13F119/TY8ePXA6nQA4nU66d+8ONB7BV1RUeJ7jcDiw\n2Wzn8zYiIuJHXov++PHjnktf1dbW8u233xIbG0tiYiL5+fkA5OfnM3z4cAASExMpKCigrq6OsrIy\nSkpKWrxCi4iIdAyvQzdOp5Ply5fjcrlwu92MGjWKa6+9lgEDBpCVlUVeXp5neiVAXFwco0aNIj09\nHavVSmpqqmbciIgYyGvRX3rppSxcuLDZ9m7dupGRkdHic1JSUkhJSWl7OhERaTMdaouImJyKXkTE\n5FT0IiImp6IXETE5Fb2IiMmp6EVETE5FLyJicip6ERGTU9GLiJicil5ExORU9CIiJqeiFxExORW9\niIjJqehFRExORS8iYnIqehERk1PRi4iYnIpeRMTkvF5KUATg+qWbfHrc2t8MbOckInK+vBZ9eXk5\ny5cv59ixY1gsFux2O7fccgsffPABGzZsoHv37gDccccdXHPNNQBkZ2eTl5eH1Wpl1qxZJCQktO9e\niIjIWXkt+pCQEKZPn058fDynT5/miSeeYNiwYQDceuutTJ48ucnji4uLKSgoYMmSJTidTubPn8/S\npUuxWjVKJCJiBK/tGxkZSXx8PABdunQhNjYWh8Nx1scXFhaSlJREWFgYMTEx9O7dm6KiIv8lFhGR\n83Jeh9llZWUcOHCAfv36AbB+/Xoee+wxVqxYwcmTJwFwOBz06tXL8xybzXbOXwwiItK+fP4wtrq6\nmsWLFzNz5kzCw8MZP348U6dOBWD16tW8++67zJ492+c3zs3NJTc3F4DMzEyioqLOM/q5hYaG+v01\n20Ow5PRVsOyLcvomGP59BkNGMDanT0VfX1/P4sWLueGGGxgxYgQAPXv29Nw/btw4FixYADQewVdU\nVHjuczgc2Gy2Zq9pt9ux2+2e2+Xl5a3bg7OIiory+2u2h2DJ6atg2Rfl9E0w/PsMhozQPjn79Onj\n0+O8Dt243W5ee+01YmNjmThxome70+n0/P/WrVuJi4sDIDExkYKCAurq6igrK6OkpMQz1CMiIh3P\n6xH97t272bhxI3379uXxxx8HGqdSbt68mYMHD2KxWIiOjubee+8FIC4ujlGjRpGeno7VaiU1NVUz\nbkREDOS16AcOHMgHH3zQbPuZOfMtSUlJISUlpW3JRETEL3SoLSJicip6ERGTU9GLiJicil5ExORU\n9CIiJqeiFxExORW9iIjJqehFRExORS8iYnIqehERk1PRi4iYnIpeRMTkVPQiIianohcRMTkVvYiI\nyanoRURMTkUvImJyKnoREZNT0YuImJyKXkTE5LxeHLy8vJzly5dz7NgxLBYLdrudW265hZMnT5KV\nlcXRo0eJjo4mLS2NiIgIALKzs8nLy8NqtTJr1iwSEhLafUdERKRlXos+JCSE6dOnEx8fz+nTp3ni\niScYNmwYX3zxBUOHDiU5OZmcnBxycnK46667KC4upqCggCVLluB0Opk/fz5Lly7FatUfDyIiRvDa\nvpGRkcTHxwPQpUsXYmNjcTgcFBYWMmbMGADGjBlDYWEhAIWFhSQlJREWFkZMTAy9e/emqKioHXdB\nRETOxesR/U+VlZVx4MAB+vXrR2VlJZGRkQD07NmTyspKABwOB/379/c8x2az4XA4mr1Wbm4uubm5\nAGRmZhIVFdXqnWhJaGio31+zPQRLTl8Fy74op2+C4d9nMGQEY3P6XPTV1dUsXryYmTNnEh4e3uQ+\ni8WCxWI5rze22+3Y7XbP7fLy8vN6vjdRUVF+f832ECw5fRUs+6KcvgmGf5/BkBHaJ2efPn18epxP\nA+f19fUsXryYG264gREjRgDQo0cPnE4nAE6nk+7duwONR/AVFRWe5zocDmw223mFFxER//F6RO92\nu3nttdeIjY1l4sSJnu2JiYnk5+eTnJxMfn4+w4cP92xftmwZEydOxOl0UlJSQr9+/dpvD0REgsD1\nSzf5/Ni1vxno1/f2WvS7d+9m48aN9O3bl8cffxyAO+64g+TkZLKyssjLy/NMrwSIi4tj1KhRpKen\nY7VaSU1N1YwbEREDeS36gQMH8sEHH7R4X0ZGRovbU1JSSElJaVsyERHxCx1qi4iYnIpeRMTkVPQi\nIianohcRMTkVvYiIyanoRURMTkUvImJyKnoREZNT0YuImJyKXkTE5FT0IiImp6IXETE5Fb2IiMmp\n6EVETE5FLyJicip6ERGTU9GLiJicil5ExORU9CIiJuf1mrErVqzg73//Oz169GDx4sUAfPDBB2zY\nsIHu3bsDjRcLv+aaawDIzs4mLy8Pq9XKrFmzSEhIaMf4IiLijdeiHzt2LDfddBPLly9vsv3WW29l\n8uTJTbYVFxdTUFDAkiVLcDqdzJ8/n6VLl2K16g+Hs7l+6SafH7v2NwPbMYmImJXXBh48eDARERE+\nvVhhYSFJSUmEhYURExND7969KSoqanNIERFpPa9H9Gezfv16Nm7cSHx8PDNmzCAiIgKHw0H//v09\nj7HZbDgcjhafn5ubS25uLgCZmZlERUW1NkqLQkND/f6aRguG/QmGjKCcvvL1L87N/2d0Oyc5O/2s\ne9eqoh8/fjxTp04FYPXq1bz77rvMnj37vF7Dbrdjt9s9t8vLy1sT5ayioqL8/ppGC4b9CYaMoJz+\nZmTOC/lnvU+fPj49rlWD5z179sRqtWK1Whk3bhz79u0DGo/gKyoqPI9zOBzYbLbWvIWIiPhJq4re\n6XR6/n/r1q3ExcUBkJiYSEFBAXV1dZSVlVFSUkK/fv38k1RERFrF69DNSy+9xM6dOzlx4gT3338/\n06ZNY8eOHRw8eBCLxUJ0dDT33nsvAHFxcYwaNYr09HSsViupqamacSMiYjCvRf/73/++2bYbb7zx\nrI9PSUkhJSWlbalERMRvdLgtImJyKnoREZNT0YuImJyKXkTE5FT0IiImp6IXETE5Fb2IiMmp6EVE\nTE5FLyJicip6ERGTa/V69IFOV24SEWmkI3oREZNT0YuImJyKXkTE5FT0IiImp6IXETE5Fb2IiMmp\n6EVETE5FLyJicl5PmFqxYgV///vf6dGjB4sXLwbg5MmTZGVlcfToUaKjo0lLSyMiIgKA7Oxs8vLy\nsFqtzJo1i4SEhPbdAxEROSevR/Rjx47lySefbLItJyeHoUOHsmzZMoYOHUpOTg4AxcXFFBQUsGTJ\nEubOncuqVatwuVztk1xERHzitegHDx7sOVo/o7CwkDFjxgAwZswYCgsLPduTkpIICwsjJiaG3r17\nU1RU1A6xRUTEV60ao6+srCQyMhKAnj17UllZCYDD4aBXr16ex9lsNhwOhx9iiohIa7V5UTOLxYLF\nYjnv5+Xm5pKbmwtAZmYmUVFRbY3Saka+9/kIhpztkfHIlCTfHzx2oU8PC4avJSinL0JDQ4Pm6+Qr\nf+9Pq4q+R48eOJ1OIiMjcTqddO/eHWg8gq+oqPA8zuFwYLPZWnwNu92O3W733C4vL29NFL8w8r3P\nRzDkDIaMoJz+ZmTOqKiooPk6+crX/enTp49Pj2vV0E1iYiL5+fkA5OfnM3z4cM/2goIC6urqKCsr\no6SkhH79+rXmLURExE+8HtG/9NJL7Ny5kxMnTnD//fczbdo0kpOTycrKIi8vzzO9EiAuLo5Ro0aR\nnp6O1WolNTUVq1VT9QNVw+8m+/5gH4dERDqarj3hndei//3vf9/i9oyMjBa3p6SkkJKS0rZUIiLi\nN6a9wpTRfD5a1pGyaegvJAlUQVf0KlARkfOjAXQREZNT0YuImJyKXkTE5FT0IiImp6IXETG5oJt1\nIyJto2mgFx4d0YuImJyKXkTE5FT0IiImp6IXETE5Fb2IiMmp6EVETE5FLyJicip6ERGTU9GLiJic\nil5ExORU9CIiJqeiFxExuTYtavbggw/SuXNnrFYrISEhZGZmcvLkSbKysjh69CjR0dGkpaURERHh\nr7wiInKe2rx65bx58+jevbvndk5ODkOHDiU5OZmcnBxycnK466672vo2IiLSSn4fuiksLGTMmDEA\njBkzhsLCQn+/hYiInIc2H9HPnz8fq9XKL3/5S+x2O5WVlURGRgLQs2dPKisrW3xebm4uubm5AGRm\nZhIVFeXT+x1pa+AW+Pre5yMYcgZDRlBOfwuanFOSfHvgeayZ3x4524O/c7ap6OfPn4/NZqOyspLn\nnnuOPn36NLnfYrFgsVhafK7dbsdut3tul5eXtyVKmxj53ucjGHIGQ0ZQTn9TTv/yNee/du7ZtGno\nxmazAdCjRw+GDx9OUVERPXr0wOl0AuB0OpuM34uISMdrddFXV1dz+vRpz/9/++239O3bl8TERPLz\n8wHIz89n+PDh/kkqIiKt0uqhm8rKShYtWgRAQ0MDo0ePJiEhgSuuuIKsrCzy8vI80ytFRMQ4rS76\niy++mBdffLHZ9m7dupGRkdGmUCIi4j86M1ZExORU9CIiJqeiFxExORW9iIjJqehFRExORS8iYnIq\nehERk1PRi4iYnIpeRMTkVPQiIianohcRMTkVvYiIyanoRURMTkUvImJyKnoREZNT0YuImJyKXkTE\n5Fp9hSkREYGG30327YFjF7ZvkHPQEb2IiMm12xH9119/zR//+EdcLhfjxo0jOTm5vd5KRETOoV2O\n6F0uF6tWreLJJ58kKyuLzZs3U1xc3B5vJSIiXrRL0RcVFdG7d28uvvhiQkNDSUpKorCwsD3eSkRE\nvLC43W63v1/0r3/9K19//TX3338/ABs3bmTv3r2kpqZ6HpObm0tubi4AmZmZ/o4gIiL/n2Efxtrt\ndjIzM9ut5J944ol2eV1/U07/Uk7/CoacwZARjM3ZLkVvs9moqKjw3K6oqMBms7XHW4mIiBftUvRX\nXHEFJSUllJWVUV9fT0FBAYmJie3xViIi4kXIM88884y/X9RqtdK7d29efvll1q9fzw033MDIkSP9\n/TZexcfHd/h7toZy+pdy+lcw5AyGjGBcznb5MFZERAKHzowVETE5Fb2IiMmp6EVETE5FLyJicir6\nDuZyuXj33XeNjmEaLpeLgoICo2N4VVpaSl1dHQA7duxg3bp1nDp1yuBUwa+mpsboCOf08ssv+7St\nvZlqPfrDhw+zcuVKKisrWbx4Md9//z3btm3jtttuMzqah9VqZffu3UbH8EltbS15eXkUFxdTW1vr\n2T579mwDUzVltVr56KOPSEpKMjrKOS1evJjMzExKS0t54403SExMZNmyZfzhD38wOloTwfA9B9i9\nezevvfYa1dXVvPrqqxw8eJDc3Fzuueceo6M18a+LObpcLvbv39/hOUx1RP/6669z5513EhISAsCl\nl14akEd7l112GQsWLGDjxo1s2bLF81+geeWVVzh27BjffPMNgwcPxuFw0KVLF6NjNTN06FA++ugj\nysvLOXnypOe/QGK1WgkJCWHr1q3cdNNNTJ8+HafTaXSsZoLle/7OO+8wd+5cunXrBjT+TH333XcG\np/pf2dnZzJgxg++//567776bu+++mxkzZnDPPfcwfPjwDs9jqiP62tpa+vXr12Sb1Rp4v8vq6uro\n1q0b//znP5tsHzFihEGJWlZaWkp6ejrbtm1j7NixjB49mnnz5hkdq5kzv8w/++wzzzaLxcIrr7xi\nVKRmQkJC2LRpE/n5+cyZMweAhoYGg1M1Fyzfc4CoqKgmtwPpZ33KlClMmTKF999/nzvvvNPoOOYq\n+m7dulFaWorFYgEaV9GMjIw0OFVzgfZn8Nmc+cuoa9eu/PDDD/Ts2ZPKykqDUzW3fPlyoyN4NXv2\nbP7nf/6HKVOmEBMTQ1lZGTfccIPRsZoJlu95r1692L17NxaLhfr6etatW0dsbKzRsZpJSEhg586d\nzbYPHjy4Q3OY6szYI0eO8MYbb7B79266du1KTEwMDz/8MDExMUZHayIYPksA2LBhAyNGjOCHH35g\nxYoVVFdXM23aNMaPH290tCZqamr45JNPKC8v57777qOkpITDhw9z7bXXGh2tidraWsrLy+nTp4/R\nUc4qWL7nx48f5+2332b79u243W6GDRvGrFmzPEM5geKnq/PW1dVRVFREfHx8x/+V5Dah06dPu6uq\nqoyOcVYZGRnuvXv3uh9//HHPtvT0dAMTBbclS5a4c3JyPF/D6upq92OPPWZwqqYKCwvdjzzyiHv2\n7Nlut9vtPnDggDszM9PgVNLRjh496n7xxRc7/H1NNXRTV1fHli1bKCsrw+VyebZPnTrVwFTNBctn\nCb/+9a+ZPHkyd955p2c4bM6cOSxYsMDgZE0dOXKEtLQ0Nm/eDECnTp0MTtTcmjVreOGFFzizhuBl\nl11GWVmZsaF+4pNPPjnn/RMnTuygJOf21ltvnfP+3/72tx2UpHV69erFoUOHOvx9TVX0CxcuJDw8\nnPj4eMLCwoyOc1bB8llCXFwcbreb5557jrS0NCIiInAH4EhfaGgotbW1nq9naWkpoaGB9U87NDSU\n8PDwJtvO5A0Ep0+fNjqCT4JllcozfvqLye12c/DgQS6//PIOzxFYPw1t5HA4mDt3rtExvEpNTeWN\nN97g0KFD3HfffZ7PEgJNSEgId911FwUFBWRkZPDQQw8FVDmdMW3aNJ5//nnKy8tZtmwZu3fvDrgP\nvC+55BI2bdqEy+WipKSEP//5zwwYMMDoWB6333670RF8Mnbs2Ca3q6qqsFgsATkFFJr+YgoJCeH6\n669n4MCBHZ7DVB/Gvv7669x888307dvX6Cg+qa6uxu12B+w/0v/4j/9g4cKFAPzwww8sW7aM8vJy\n3n77bWODteDEiRPs3bsXt9tN//796d69u9GRmqipqeHDDz/k22+/xe1287Of/YzbbruNiy66yOho\nTVRUVPDWW295TuobOHAgs2bNolevXgYna2rfvn2eD4vdbjddu3blgQceCLoj/o5iqqJPS0ujtLSU\nmJgYwsLCcLvdWCwWFi1aZHS0Jo4dO8af/vQnnE4nTz75JMXFxezZs4cbb7zR6GhN7N+/v8kPTlVV\nFYWFhYwZM8bAVM21dKZheHg40dHRnumC4pv58+czevRofv7znwPw5Zdf8uWXX/L0008bnKypxx57\njNTUVAYNGgTArl27WLlyZcD9rO/atYs1a9ZQXl5OQ0ODp5M6+hwPUw3dPPnkk0ZH8MmKFSsYO3Ys\n2dnZAPzbv/0bWVlZAVf0WVlZTJo0yTO1Ljw8nK+++irgin7VqlXs37+fSy+9FLfbzY8//khcXBxV\nVVXcc889/OxnPzMs29tvv83MmTPJzMxscdjrzMlTgeL48eP84he/8NweO3Ysn376qYGJWma1Wj0l\nD41/eQTUKGgaAAAJvklEQVTiL/XXXnuNu+++m/j4eEMnXJii6KuqqggPDw/YIZB/deLECZKSksjJ\nyQEax+4CcdZNSEgIO3bsoKioiHvvvZfQ0FAcDofRsZqJjIxk4cKFxMXFAY3ri6xevZq77rqLRYsW\nGVr0Z46MJ0+ebFiG89GtWzc2btzI6NGjAdi0aVPAzU2HxhOO3njjDa6//nosFgsFBQUMHjzY89dd\noAzhhIeHc/XVVxsdwxxFv2zZMp544gnmzJmDxWJpMjMk0E6Fh8bpfydOnPAc4e3Zs6fZjIxA0KlT\nJ9LS0li7di0ZGRmkp6cH5IexJSUlnpKHxg8+Dx8+zMUXX2xgqkbx8fG4XC5yc3N55JFHjI7j1QMP\nPMBbb73FO++8g8ViYcCAAQH3wTbA999/D8B///d/N9l+8OBBgIBZtuGqq67ivffeY8SIEU1mgnX0\nLyJTFP0TTzwBwJVXXsngwYMZNGhQQJ4OfcaMGTNYuHAhR44c4emnn+b48eOkp6cbHauZM78wf/Wr\nX3H55Zfz3HPPBdxiYQCxsbG8+eabXH/99UDj2jexsbHU1dUFxDRLq9XK0aNHqa+vD4g857J69Woe\nfPBBIiIiADh58iTvvvtuwJV9oBS5N0VFRUDzz5E6Or+pPoz95z//ya5du/juu+84cuQIl19+OYMG\nDeKWW24xOloTtbW1rF+/nm+++YYuXbowYMAAbrrppoCbgbFt2zYSExM9t48ePUp+fn5AnoD22Wef\nsWvXLqDxF/6ECRMICwujtraWzp07G5ywcVXIQ4cOce211zbJEygnIp3x05lW59pmtBMnTrBmzZom\ns4OmTp0akMNMgSCwDy/O05AhQxg8eDBFRUXs2LGDzz//nB9//DHgiv6VV14hPDycKVOmAI3joK+8\n8krAHNUfOnSI2NhYbDZbsyORa665xqBULXO5XLz22ms88sgjTJo0qdn9Rpf8yy+/zMMPP8y2bdu4\n9dZbcbvdAX1yktvt5uTJk02O6ANxlc2XXnqJQYMG8eijjwKNs4NeeumlgJsdVFVVxZo1azxLKA8e\nPJipU6d2+FCtqYr+2Wefpaamhv79+zNo0CBeeOEFevToYXSsZn788UeysrI8t4cMGUJaWpqBiZr6\n5JNPuO+++3jvvfdavD+Q/mwO9GGR/fv343A4iIqK4uabbzY6jlcTJ07kqaeeYuTIkUDjWdspKSkG\np2ru2LFjTf6yvO222wLy2hMrVqygb9++np/vjRs3smLFCh577LEOzRHyzJnFN0zgwIEDHD9+nJMn\nTxIaGkqnTp3o2bNnwE272rNnD5GRkZ6TUPbu3YvD4eC6664zOFmjM8M1SUlJVFVVUVlZyUUXXcSw\nYcOYOXNmwH09d+7cydq1azl27Bj79+9nz5497NmzJyDOPHW5XPzxj3/kyJEjbN68mdzcXHJzc/n8\n88/ZsGFDwP21edlllzFkyBCOHz9O586dSU5OZujQoUbHaqa0tJRTp05xySWX4Ha7+eqrr7jooosM\nnWHVkuzsbM/yIREREVx11VVkZ2d3+GqgphqjP+P06dN88cUXfPzxxxw7doz333/f6EgAPProo1gs\nFhoaGjh8+LDnwglnlq796VF+IFiyZAnh4eFNptpVVVUFzBDTGWvWrGlxeyCd1v/mm2/yu9/9zugY\npjFjxgxqamo805JdLpdnMTuLxcI777xjZDyPuXPnMn36dM+yB7t27eK9997j+eef79Acpir69evX\n891337F//35iYmIYOHAggwYNYsiQIUZHAxo/zDyX6OjoDkrim7S0tGa/fFraJmKEkydPUlJS4rno\nOnT8BT28OXjwIMuXL6eqqgpovKDLgw8+yKWXXtqhOQJvULMNamtrmThxIvHx8QE3vACBV+TeXH75\n5U2GQPbu3csVV1xhcKrm/vM//7PF7YH0WYL414YNG1i3bh0Oh4PLLruMPXv2cOWVV5KRkWF0NKDp\nss8///nPqampARrPTdm+fbuKvi2C5ezDYHHgwAGefvrpZkNMZ4agAmVdkenTp3v+v7a2li1btgTk\nL3rxn3Xr1vHCCy8wd+5c5s2bx6FDh/jTn/5kdCyPMzOrDh8+zL59+zyfe3355ZeGHCyZqujFv4Jl\n7aB/Pctw4MCB/OEPfzAojXSEiy66yHPeSV1dHbGxsRw+fNjgVP/rzOdD8+bNY8GCBZ7lWW6//fYm\nlxfsKCp6OatgGWr66dm6LpeL/fv3e8ZExZxsNhunTp1i+PDhPPfcc3Tt2jUg/70eO3asybTf0NBQ\njh071uE5TPVhrFyYHnzwQc8aPCEhIURHRzN16lRDLvAgHW/nzp1UVVWRkJAQcOdSfPjhh3z11VcM\nHz4cgMLCQpKSkjwnS3YUFb0EvZ8ugWCxWBg4cCDjx48PuCUl5MK0f/9+z/IcgwYNMuRSgip6CXrB\nMt9fxCiB9XeOSCsE+pISIkYLvKtdiJynM/P9zwjU+f4iRtERvQStny4p0dJ8fxFppDF6CVrBtqSE\niFFU9CIiJqcxehERk1PRi4iYnIpexE+++OKLgLuUnQho1o1cQB588EGOHTvmuVgFwNKlS7HZbAam\nEml/Knq5oMyZM4dhw4YZHUOkQ6no5YK3bds23n//fc9FLO655x4uueQSAIqLi1m5ciUHDx7EZrNx\n5513etYWP3HiBCtWrGDnzp306dMn4K5XKnKGxujlgnb48GGWLl3KzJkzWblyJVdffTULFiygvr6e\n+vp6FixYwLBhw1i5ciW//e1vWbZsmWfd81WrVhEWFsbrr7/OAw88wF/+8heD90akZTqilwvKiy++\n6Ln61ODBg4mPj+fqq6/2DOdMmjSJdevWsXv3bqxWK9XV1SQnJ2O1WhkyZAjXXHMNmzZtYurUqWzZ\nsoVFixbRuXNn+vbty5gxY/juu++M3D2RFqno5YLy+OOPNxmjf/PNN5ucQWu1WomKisLhcBASEkJU\nVFSTD2+jo6NxOBwcP36choYGevXq1eQ+Fb0EIg3dyAUtMjKyyVIKbreb8vJybDYbkZGRlJeX43K5\nPPefua979+6EhIRQUVHR5D6RQKSilwtaUlIS//jHP9i+fTv19fV8/PHHhIWFceWVV9K/f386derE\nRx99RH19PTt27OBvf/sb119/PVarleuuu441a9ZQU1NDcXEx+fn5Ru+OSIs0dCMXtD59+vDwww/z\n1ltveWbdzJkzx3NJujlz5rBy5Uqys7Ox2Ww89NBDxMbGApCamsqKFSu499576dOnD2PHjmXHjh1G\n7o5Ii7SomYiIyWnoRkTE5FT0IiImp6IXETE5Fb2IiMmp6EVETE5FLyJicip6ERGTU9GLiJjc/wMi\nFuZkE0nlkwAAAABJRU5ErkJggg==\n", "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "data.plot(kind=\"bar\", x=\"Food\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Tackling the Problem\n", "\n", "The objective is to find the set of menu items with the highest value while still amounting to less than or equal to 750 calories. For instance, Dave could pick:\n", "\n", "- wine\n", "\n", "- burger\n", "\n", "- donut\n", "\n", "Which has a total value of 234 and a total cost of 476 calories. This is a valid choice, but is not optimal.\n", "\n", "## Finding an Optimal Solution\n", "\n", "Finding an optimal solution is straightforward:\n", "\n", "1. Gather all possible sets of items\n", "\n", "2. Eliminate invalid sets (i.e. sets with calorie counts larger than 750)\n", "\n", "3. Sort the sets by value\n", "\n", "4. The first set in the sorted list of sets is the optimal solution\n", "\n", "### Implementation\n", "\n", "I am not familar enough with Pandas to use it properly, so I'm going to convert the data into a regular Python list." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]]" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "menu = data.values.tolist()\n", "menu" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": true }, "outputs": [], "source": [ "# Set constant\n", "CALORIE_LIMIT = 750" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def power_set(set_):\n", " \"\"\"Binary powerset algorithm.\"\"\"\n", " power_set = []\n", " \n", " power_cardinality = 2**len(set_)\n", " \n", " # the number of binary digits needed\n", " digit_count = len(set_)\n", " \n", " # setting up the formatting\n", " format_spec = '0' + str(digit_count) + 'b' \n", " \n", " for n in range(power_cardinality):\n", " subset = []\n", " \n", " binary_n = format(n, format_spec)\n", " \n", " # for every character in a binary number\n", " for i, char in enumerate(binary_n):\n", " if char == '1':\n", " # when char is 1, the element in set_ with matching index is present in the subset\n", " subset.append(set_[i])\n", " \n", " power_set.append(subset)\n", " \n", " return power_set" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[],\n", " [['donut', 10, 195]],\n", " [['apple', 50, 95]],\n", " [['apple', 50, 95], ['donut', 10, 195]],\n", " [['cola', 79, 150]],\n", " [['cola', 79, 150], ['donut', 10, 195]],\n", " [['cola', 79, 150], ['apple', 50, 95]],\n", " [['cola', 79, 150], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['fries', 90, 365]],\n", " [['fries', 90, 365], ['donut', 10, 195]],\n", " [['fries', 90, 365], ['apple', 50, 95]],\n", " [['fries', 90, 365], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['fries', 90, 365], ['cola', 79, 150]],\n", " [['fries', 90, 365], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['fries', 90, 365], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['burger', 100, 354]],\n", " [['burger', 100, 354], ['donut', 10, 195]],\n", " [['burger', 100, 354], ['apple', 50, 95]],\n", " [['burger', 100, 354], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['burger', 100, 354], ['cola', 79, 150]],\n", " [['burger', 100, 354], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['burger', 100, 354], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['burger', 100, 354], ['fries', 90, 365]],\n", " [['burger', 100, 354], ['fries', 90, 365], ['donut', 10, 195]],\n", " [['burger', 100, 354], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['burger', 100, 354], ['fries', 90, 365], ['cola', 79, 150]],\n", " [['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258]],\n", " [['pizza', 95, 258], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['apple', 50, 95]],\n", " [['pizza', 95, 258], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['cola', 79, 150]],\n", " [['pizza', 95, 258], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['fries', 90, 365]],\n", " [['pizza', 95, 258], ['fries', 90, 365], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['fries', 90, 365], ['cola', 79, 150]],\n", " [['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['burger', 100, 354]],\n", " [['pizza', 95, 258], ['burger', 100, 354], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['burger', 100, 354], ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['burger', 100, 354], ['cola', 79, 150]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['burger', 100, 354], ['fries', 90, 365]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154]],\n", " [['beer', 90, 154], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['apple', 50, 95]],\n", " [['beer', 90, 154], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['cola', 79, 150]],\n", " [['beer', 90, 154], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['beer', 90, 154], ['cola', 79, 150], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['fries', 90, 365]],\n", " [['beer', 90, 154], ['fries', 90, 365], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['fries', 90, 365], ['cola', 79, 150]],\n", " [['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['fries', 90, 365], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['burger', 100, 354]],\n", " [['beer', 90, 154], ['burger', 100, 354], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['burger', 100, 354], ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['burger', 100, 354], ['cola', 79, 150]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['burger', 100, 354], ['fries', 90, 365]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['cola', 79, 150]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['fries', 90, 365]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['burger', 100, 354]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123]],\n", " [['wine', 89, 123], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['cola', 79, 150]],\n", " [['wine', 89, 123], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['cola', 79, 150], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['fries', 90, 365]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['burger', 100, 354]],\n", " [['wine', 89, 123], ['burger', 100, 354], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['burger', 100, 354], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['burger', 100, 354], ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['burger', 100, 354], ['fries', 90, 365]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['fries', 90, 365]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['burger', 100, 354]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['cola', 79, 150]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['fries', 90, 365]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['fries', 90, 365], ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['burger', 100, 354]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['pizza', 95, 258]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['pizza', 95, 258], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['pizza', 95, 258], ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]]]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The powerset is the list of all possible sets of items\n", "menu_power = power_set(menu)\n", "menu_power" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To help eliminate invalid sets, I'll write a function which calculates the sum of a given set." ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def valid_choice(choice):\n", " \"\"\"(list) -> bool\n", " Given a list of chosen foods, return true if their total cost exceeds CALORIE_LIMIT\"\"\"\n", " total_cost = 0\n", " for food in choice:\n", " total_cost += food[2]\n", " \n", " return total_cost < CALORIE_LIMIT" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[],\n", " [['donut', 10, 195]],\n", " [['apple', 50, 95]],\n", " [['apple', 50, 95], ['donut', 10, 195]],\n", " [['cola', 79, 150]],\n", " [['cola', 79, 150], ['donut', 10, 195]],\n", " [['cola', 79, 150], ['apple', 50, 95]],\n", " [['cola', 79, 150], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['fries', 90, 365]],\n", " [['fries', 90, 365], ['donut', 10, 195]],\n", " [['fries', 90, 365], ['apple', 50, 95]],\n", " [['fries', 90, 365], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['fries', 90, 365], ['cola', 79, 150]],\n", " [['fries', 90, 365], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['fries', 90, 365], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['burger', 100, 354]],\n", " [['burger', 100, 354], ['donut', 10, 195]],\n", " [['burger', 100, 354], ['apple', 50, 95]],\n", " [['burger', 100, 354], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['burger', 100, 354], ['cola', 79, 150]],\n", " [['burger', 100, 354], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['burger', 100, 354], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['burger', 100, 354], ['fries', 90, 365]],\n", " [['pizza', 95, 258]],\n", " [['pizza', 95, 258], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['apple', 50, 95]],\n", " [['pizza', 95, 258], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['cola', 79, 150]],\n", " [['pizza', 95, 258], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['pizza', 95, 258], ['fries', 90, 365]],\n", " [['pizza', 95, 258], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['pizza', 95, 258], ['burger', 100, 354]],\n", " [['pizza', 95, 258], ['burger', 100, 354], ['apple', 50, 95]],\n", " [['beer', 90, 154]],\n", " [['beer', 90, 154], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['apple', 50, 95]],\n", " [['beer', 90, 154], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['cola', 79, 150]],\n", " [['beer', 90, 154], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['beer', 90, 154], ['cola', 79, 150], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['fries', 90, 365]],\n", " [['beer', 90, 154], ['fries', 90, 365], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['beer', 90, 154], ['fries', 90, 365], ['cola', 79, 150]],\n", " [['beer', 90, 154], ['burger', 100, 354]],\n", " [['beer', 90, 154], ['burger', 100, 354], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['burger', 100, 354], ['apple', 50, 95]],\n", " [['beer', 90, 154], ['burger', 100, 354], ['cola', 79, 150]],\n", " [['beer', 90, 154], ['pizza', 95, 258]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['apple', 50, 95]],\n", " [['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['cola', 79, 150]],\n", " [['beer', 90, 154], ['pizza', 95, 258], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123]],\n", " [['wine', 89, 123], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['cola', 79, 150]],\n", " [['wine', 89, 123], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['cola', 79, 150], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['fries', 90, 365]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['cola', 79, 150]],\n", " [['wine', 89, 123], ['fries', 90, 365], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['burger', 100, 354]],\n", " [['wine', 89, 123], ['burger', 100, 354], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['burger', 100, 354], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['burger', 100, 354], ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['burger', 100, 354],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123], ['pizza', 95, 258]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['cola', 79, 150]],\n", " [['wine', 89, 123],\n", " ['pizza', 95, 258],\n", " ['cola', 79, 150],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['fries', 90, 365]],\n", " [['wine', 89, 123], ['pizza', 95, 258], ['burger', 100, 354]],\n", " [['wine', 89, 123], ['beer', 90, 154]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['apple', 50, 95], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['cola', 79, 150]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['cola', 79, 150], ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['cola', 79, 150], ['apple', 50, 95]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['fries', 90, 365]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['fries', 90, 365], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['burger', 100, 354]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['burger', 100, 354],\n", " ['apple', 50, 95]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['pizza', 95, 258]],\n", " [['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['donut', 10, 195]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['pizza', 95, 258], ['apple', 50, 95]],\n", " [['wine', 89, 123], ['beer', 90, 154], ['pizza', 95, 258], ['cola', 79, 150]]]" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Collect valid sets\n", "valid_choices = []\n", "for choice in menu_power:\n", " if valid_choice(choice):\n", " valid_choices.append(choice)\n", "\n", "valid_choices" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To help sort the valid choices by value, I'll write a function to calculate the total value of a given choice." ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def total_value(choice):\n", " \"\"\"(list) -> int\n", " Given a list of foods, returns the sum of their values.\"\"\"\n", " total_value = 0\n", " for food in choice:\n", " total_value += food[1]\n", " return total_value" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The optimal menu choice is [['wine', 89, 123], ['beer', 90, 154], ['pizza', 95, 258], ['cola', 79, 150]]\n" ] } ], "source": [ "sorted_choices = sorted(valid_choices, key=total_value, reverse=True)\n", "\n", "print(\"The optimal menu choice is\", sorted_choices[0])" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Total value: 353\n" ] } ], "source": [ "print(\"Total value:\", total_value(sorted_choices[0]))" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Total cost: 685\n" ] } ], "source": [ "total_cost = 0\n", "for food in sorted_choices[0]:\n", " total_cost += food[2]\n", "\n", "print(\"Total cost:\", total_cost)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This was fun, but my implementation isn't the best. In the course, the data is converted into objects (e.g. there is a Food class). Hmm...I wonder what the best way to carry out this kind of analysis is? Maybe I'll look into this. *Moving on...*\n", "\n", "## Greedy Algorithms\n", "\n", "Finding the optimal solution is computationally expensive, just computing the powerset costs $O(2^n)$! This dataset is small enough that I can be as inefficient as I want, but this does not scale. Greedy algorithms offer a way to determine a \"good\" (but not optimal) solution in a lot less time.\n", "\n", "A greedy algorithm for the 0/1 knapsack problem is:\n", "\n", "\n", "while knapsack is not full:\n", " put \"best\" available item into it\n", "\n", "\n", "The definition of \"best\" is up for debate. It could mean:\n", "\n", "- highest value\n", "\n", "- lowest cost\n", "\n", "- highest ratio of value to cost (value/cost)\n", "\n", "### Implementation\n", "\n", "Fairly simple:\n", "\n", "1. Sort the data set by the criteria we think is \"best\"\n", "\n", "2. Loop through the sorted set, taking items until reaching the limit" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "menu" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[['burger', 100, 354],\n", " ['pizza', 95, 258],\n", " ['beer', 90, 154],\n", " ['fries', 90, 365],\n", " ['wine', 89, 123],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['donut', 10, 195]]" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Sorted from highest to lowest value\n", "by_value = sorted(menu, key=lambda food: food[1], reverse=True)\n", "by_value" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[['apple', 50, 95],\n", " ['wine', 89, 123],\n", " ['cola', 79, 150],\n", " ['beer', 90, 154],\n", " ['donut', 10, 195],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365]]" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Sorted from smallest to largest cost\n", "by_cost = sorted(menu, key=lambda food: food[2])\n", "by_cost" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[['wine', 89, 123],\n", " ['beer', 90, 154],\n", " ['cola', 79, 150],\n", " ['apple', 50, 95],\n", " ['pizza', 95, 258],\n", " ['burger', 100, 354],\n", " ['fries', 90, 365],\n", " ['donut', 10, 195]]" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Sorted from greatest to least value/cost (i.e. best \"bang for your buck\")\n", "by_ratio = sorted(menu, key=lambda food: food[1]/food[2], reverse=True)\n", "by_ratio" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def order_to_limit(menu, criteria):\n", " \"\"\"(list, str) -> None\n", " Given a menu, orders as many items as possible (until reaching CALORIE_LIMIT).\n", " Prints the results.\"\"\"\n", " cost = 0\n", " value = 0\n", " ordered = []\n", " for food in menu:\n", " f_cost = food[2]\n", " f_value = food[1]\n", " f_name = food[0]\n", " \n", " # If the calorie cost + calories already consumed does not exceed limit\n", " if ((cost + f_cost) < CALORIE_LIMIT):\n", " # Order the food\n", " cost += f_cost\n", " value += f_value\n", " ordered.append(f_name)\n", " \n", " print(\"With {} criteria:\".format(criteria))\n", " print(\" food ordered:\", ordered)\n", " print(\" total calories:\", cost)\n", " print(\" total value:\", value)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "With VALUE criteria:\n", " food ordered: ['burger', 'pizza', 'wine']\n", " total calories: 735\n", " total value: 284\n", "\n", "With COST criteria:\n", " food ordered: ['apple', 'wine', 'cola', 'beer', 'donut']\n", " total calories: 717\n", " total value: 318\n", "\n", "With RATIO criteria:\n", " food ordered: ['wine', 'beer', 'cola', 'apple', 'donut']\n", " total calories: 717\n", " total value: 318\n" ] } ], "source": [ "# Run some computations, print the results\n", "order_to_limit(by_value, \"VALUE\")\n", "print()\n", "order_to_limit(by_cost, \"COST\")\n", "print()\n", "order_to_limit(by_ratio, \"RATIO\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For comparison,\n", "\n", "\n", "Optimal solution:\n", " food ordered: ['wine', 'beer', 'pizza', 'cola']\n", " total calories: 685\n", " total value: 353\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Though none of the greedy results matched the optimal solution, they were close. They are also far more efficient; $O(n \\log n)$, if I'm not mistaken.\n", "\n", "**tl;dr**: Dave should order wine, beer, pizza, and a cola. \n", "\n", "> **DAVE:** \"Three drinks and a pizza isn't a meal.\"\n", ">\n", "> **SCIENTIST:** \"FOOL! You should have been more specific with your constraints!\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Total costTotal pleasure
000
119510
29550
329060
415079
534589
6245129
7440139
836590
9560100
10460140
11655150
12515169
13710179
14610219
15354100
16549110
17449150
18644160
19504179
20699189
21599229
22719190
2325895
24453105
25353145
26548155
27408174
28603184
29503224
.........
70477189
71672199
72572239
73627268
74722318
75381184
76576194
77476234
78671244
79531263
80726273
81626313
82746274
83735284
84277179
85472189
86372229
87567239
88427258
89622268
90522308
91717318
92642269
93737319
94631279
95726329
96535274
97730284
98630324
99685353
\n", "

100 rows × 2 columns

\n", "