{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![alt text](https://github.com/callysto/callysto-sample-notebooks/blob/master/notebooks/images/Callysto_Notebook-Banner_Top_06.06.18.jpg?raw=true)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Introduction to Dynamic Programming\n",
"\n",
"## We solve a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.\n",
"\n",
"### The key idea is called \"memoization\" (not \"memorization\") and the details appear in this YouTube video"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEABALDA4MChAODQ4SERATGCgaGBYWGDEjJR0oOjM9PDkzODdASFxOQERXRTc4UG1RV19iZ2hnPk1xeXBkeFxlZ2MBERISGBUYLxoaL2NCOEJjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY//AABEIAWgB4AMBIgACEQEDEQH/xAAbAAEAAgMBAQAAAAAAAAAAAAAABAUCAwYBB//EAEUQAAEEAgAEAwYDBQYFAQkBAAEAAgMEBREGEiExE0FRFCIyYXGBFUKRM1KhscEHIyRD0fAWYnKC8eEmNDZEU2OTosIl/8QAGQEBAAMBAQAAAAAAAAAAAAAAAAECAwQF/8QAMREBAAIBAwEFBgYCAwAAAAAAAAECEQMSITEEE0FRYTJxgZGhsRQiUsHR4ULwM2Lx/9oADAMBAAIRAxEAPwD5+iIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIu04M4TrZehLcyAk5C/liDHa3ruf9+ig8acOR4OzA+pz+zSt17x2Q4d/4aQcyimw4nIWKvtUNOaSDr77W7HTusrWFyVOuJ7NKaKI/mc3p/6IICKdTw+Rvs56lKaVv7zW9P1WyripmZqrSyEEsPiyta5rhokE66IK1F2PFnCsVCzUgxEE8r5Wvc5u+Y6Gv9VzL8bdjuNpvrStsO7RlvvFBERTn4bJMssrOpTiZ421nIdkeq9tYbJUi32qlNFzHQJb0J9NoICLqOLsJRxcVJ2PZY/vARJ4gPfpruO/foqk8P5dsHjnHWPD1vfIf5IK1EUujjLuQJFOrLNrvyN2B90ERFMtYu9SlbHZqTRPedNDmH3vp6ruMfwbiq2Gjt5gymR7Q53KSAzfloIPnaLbZEbbEohO4g88h9Rvou0xfCOPvYSCdzpWzyx75uboD9FMRM9FbXivVwyK+oYFzeI2Y3IscGnZ2065hroQVs4rwtfF260NJsh8VpJBPMSdpicZN8Zw51FYnB5QQ+KaE4YBvfIp/C+JqZF9k3WzFsbRy8gPf7JETJNoiMufRT5MTdEckzKsxgYXe+W+QWutjbtuMyV60krAdFzW7CYTmERFMqYu9daXVassrR5tb0WixWmqymKxE+J4/K4aKgzDUitOHaMOSzEVaxzeG4EnlOj0C62Xhfh+GzHWlllZNKNsYZOrvp0VorMq21IrOJfPkV/xTgG4aaJ0L3Pgm3rm7tI8lXxYXJTQ+NHSndH33yd1GJTFomMoCLZ4Uhl8IRu8TeuXXXfppTJMLk4YTNJRmbGBsuLewUJzEK9FLkxt2KqLMlaRsBAIeW9OvZenGXhWbY9ll8FwBD+Xod9lODMIaKwOFyYexhpTBz/hHL3WDcRkH2HV205jK3q5vL2TEm6PNCRWdXFTMytarerzRNkfojlOyPPSm5zBGPKuhxVaeSIRhxBaeh6+vkmJRujOHPopLKFp9o1W15DO3vGG9Qsjjbos+zeyy+PrfJynekwnMIiKXbxl2k0OtVZYmnsXN6KIoTE56CLoeDsCzO5F7bHMKsTdvLToknsN/wC+yuOLuD6mMxPtmOEu43DxA93N7p6b/VBwyKVSxtzIc/sdaSbk1zcg3rfb+S3yYHLRQGd+PsNiHdxYeiCuRTKeKv3onSVKkszGnRcxuwCs7GEydWt7RPRnji1vmLOg+voggIpsOJvz1TahqSvgAJMjW9Onde2MPkascclilNG2Q6YSw9T6IIKKzdw9mGQ+M7HWAzW98h/koVepYtTeFXhklk/dY0koNKKfcwmToxeLapTRR/vFvQLXRxd7I79jqyzcvcsb0H3QREXS8O8OOsZ5tHL15oWujc8D4SdfNe57haxDmZq+Ip2JoI2tO+/UjZ6oOZRZyxPhkdHKxzHtOi1w0QsEBbqdaS5birxDb5XBrfutKn4XJuxGRZdZDHM9gPKH70Cem+iD6zNjJK/DwxmPlZA8RiNsjvL1P17rTxHi35bhuSB/K+yxge0t7F4Hl9f6r5vn+JLmcmifKGwiJpAbGTr6rfgeLruEqyQRxxzse/n/AL0nodIOz4SsGnwILAbzGFsr+U+enFb8VkJc7wfYsXWRlz2StIaOhA3pcW3jOyzG2KMdOuyKbn7b93nJJ11+a04vi21jMO/Gx14Xxu5vedvfvIOxxDsjFhKM1i1FjqUcbGhoZzvk9N+m/Qeq3cXsBu4N/LtwutG9dguTpcd3auNjqPq15jE0NY9+/LtsLO1/aBdswxsNOu0tc1xPU70Qft2QX3GuSdic3hrjd6Zz84Hm08uwugdQp2MlBmfdLmQFrXa6EHqDv6b/AFXzDM5u5xVbqQurxskaSxgj31LiPX6LseKbY4e4TgxsMhM0jBC0768oHvH+n3QRsJxPBNxFkrNlrxXdysjn5SWxtG9bPlvup3FMNx9CKeO2yek6xE8hzRtoLhrlI7jr5rhOH+IrGBfMYYopWTAB7ZAfL/yp2X42u5OGOAQRQQte15a3Z5tHYH02EHX8YzNrWMNM6F04ZZ2Y2t5i7p5BWbrLsrX8fEX2hzOjo3s2CfRw7gr55kuNLt+anKa8EbqkniM1s7Pz6qbJ/aLeMDmxU68crh+0Gz99IOQnjdDPJFJ0exxa76hfVmPfhuB45sVCJJWwteABvZOtu+fclfJ5JHSSOke4uc4kknzK6LB8Z5DD1RV5I7EDfhbJsFvyB9EHdvuzTcIjJXYGNtQxeOGuboB7eo6eW9fxXnEmWno8Li7G1hkka0EOHT3h1XB53jG/mq5rOayvAfiZHvbvqV5lOLbWUw7cbLXhZG3l99u9+6g55fUMXYNThCCw1ocYq/Po+el8vXXYvNumwM1OxJDBXijERdylziD03ratF4rEzLO+nOpiIdZSno5mKvfiAc+MnlP5mEjq0qqzfjjinGGrE2WURv0HHQHzKosRcoYicyVcudOGnRyQOLXfops+ar2MnXvDKQMkhaWhogfpwPffVJ1q45+0qx2a8W46e90uONhlmSG5eZYscocY2R8oYCoPDzBHlcyGt5R7RsAKN/xNCZg9lykBrTtxuBP32tbM65tmSZt7GnnAHKeYa1v5/NO/08/1Kv4XVxPH1hnwrfbNYyOMmOw2V7mA+bSTsf79VnmHQ8OcNeyV3afKSxp8+vc/oqCpCKmV/EIstR8TnLi3mOjvuFtzf/8AtTxyT5WgwRt5WsY46HqVHfVw0/DX358HW2mx0sVE2G0KUMehziPm6f781zvGtilexVeeCRssrJOXnDCNgg7G/stuNy8tKq2vLk8fYYwaaXuOwP6qLm7P4zEyGTJ4+KJjuYNZvv27/dLa1JhWnZ9Stsz+yr4M/wDiSv8AR38iu7ty40ZqrDZiBtuaTC9w2B17A+q4vFVY8XfZbhylF72bADnHXUKVlXy5S7Ba/EcfFJAPcLJD6780rrViFr9nva2VxnoZLHEeJistaaRc4j5v1vR/QfxVnkLcdO1A+e+K8X/0zHsP+65/JX7eRrCJ1nGMc14eyRkx5mkeYUmHOXGwhtixi5XD8xl7/ZW76nmz/DamI4TqsNCxxHJchAdIYGnfKR12Rvr8gBtVOdzOZbcuUYqHNXLC0ERuJ5SPi2o812y/KMv/AIxQjkY3kDG75eX0PqrCxxE2Su6I3qDS5paXNDnfw2qzrUxjP0Xjs+pE5xn4ssvG+XgSJsbHPd4UXRo2fJbp4nw8HV4pWlr2MiDmnuDzNVfjuIK+OpMqnJQSiMcrHGB+wPTovLfEVW5TNeXIw6JBLhXfvod/0U99SeeflKv4fUjjjr5wu+IsyMLTjmEIle9/K0E6A9VAwXEcFx1h1kOrmWX+7e4e6egAHN238vmqnN5SjmoYopslFGI3cw5K7+v6rPC5aliKzq7MjDLEXc+n1373/sJ30Z/qUx2a2zpz74Wt6tbjz2IfNO2eFsj2tcW6cCW9jroeywy+R/DuLaTnHUUsXhv+hPQ/rpQrWdr2b1aycpC1tdxcyIQP0SRrZUHNWaGZsMmmykUbmN5QGQP/AKqJ1q+GflKY7Pfxx084dk6nVp3rWWdoOdEA4+mu5/l+ihcMStu07WQ6CexK4udrZaB0aPsFSXM1WuYr8Pky0YZoNdI2B/M4D1UfDZCnhi72fLh8b+ro313a36qe+rn+pV/DX289fe6J1ylZx1mnZvi44tdv+6II6egHkvma7y3xXTlrSsjsta57CNtgdv8AiuGhkEU8chYHhjg7lPY68lE3i3RpTTmkcvrHBuLOL4eYXANsWB4rubprfYH7aU6hQmdh5aOTmjsuk5w5zd9Wu/8AK+c5rjK7l6AqOhirs5gSYt7OvJQsFxBbwlt08WpeZvKWSE6Khd2XAFKTHZPNVJfiidG36j3tH9FbYDK37+Uyde5AGwQP5YnchGxsjXz7KBwVl35vI5K3LBHC/kiaRHvR1z9eqqstx7er2bVSGtA18cjmCXqT0Ot6QdHwxFFWfmo64AYy67lA7D3R0/Ve8L5G7maVv8TrtaGyFjRyFoc3XbRVb/ZzK+TDXppHFz3WXOLj5nlCo8h/aBkZq8leKCGBx20yN2T9vRB1nDLoaXDc7gNwQSznQ82hx/oo3DfEbeJLpbLXbE6sC9rebm2T0B+oG/1XGUOLbdHCPxbIInxva9pkdvm97e/5qpxmSs4q6y1UfySN6dRsEehQfU6uVyUvF9nHyV9UWR7a/kPy67+5UZtS3DxLk2YdkEPjMjdLM8bEbuu9N8ye659/9o98w8raVdsmvj2SP0VXiOMMhjblmw8NsmyeaQP6dflrsg+jAtscP22SWhe0yRj5OQAEgHY18lG5pMNwbG/EVhNIyJpa0N3snW3EDv6rlWf2i3GB4FCsGn4QNjX+qjY/j3JUzIJIop43vLg07HJvyB9EF1gMnk8pxPTlydTwC2vIGHkLQ/qN9/srh+dsDjWPDtYwQGMuc78xPKT/AEXGTcc3ZcpBe9lgBgY9jWdde9re/wBAoZ4osniNua8CLxmt5fD68vw6/qgl/wBorGM4lJa0AvhaXa8z1H9Fyyss9mJc5f8Aa542Ru5AzlZvXT6qtQEREBERAREQEREGUcj4nh8bix7TsOadELOe1YskGxPJKR2L3l2v1WpEBERAREQEREBERAXu14iAiIgIiICIiAiIgbREQEREBFuqVZrtlletGZJZDprR5q6scGZivHI98UZEcfiO08Hp/qg59FZ3cDfo46G/Yja2CbXIQ4E9RsdFXxQyTytiiaXvedNaB1JQYIra1w5kat6Ck+Nr7M422NjtkD5+i2nhTKNyTaEjIo53tLmB0g08D0QUiLdbqzU7L69mMxyxnTmnyWlAREQEREBERBugt2K2/Z55Yubv4by3f6LU5znuLnkucTsknZK8RBvguWqzCyCxLE0nZDHloP6LQTtEQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQdZ/Z1NAzPeFJBzzSNPhSfuaB3+oXbc1e7azDHQ78FgifzHYd7pP6dR+i+bcPR5arbjyGNrCRzdhpfrl6jR8wryG/xPDLckbTr81x3NJst6dNdPe9FWb1jiZWilp5iHSSTwQcN4YWMe28yQRR8jmh3LtvxaIK21OHcfT4mdcrwsj1BtsbR7rXE62B5dFztTM8U1K8NdlKqY4WBg25uyAND8y2YjI51nEPtuSg5oZWeG9rHt0weRA2o72mesJ7u/kncJvbNYzWXna6WwJ3M90bcGtGwB/L7KHxbUi9ircS1PHr2udji2Unfy6b6a+Sjzx5XBZyzYwWrFWyecsPUbPkQdLVJ+NcTZKvXyzBWpxu53gDlbr9epUxes9JRNLR4N/8AaRVjfXx+RADZZByP+Y1sfp1/VcGuo46zTclkWVYA5sFQFo5hrmce516dAuXVlRERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBFNxeKuZax4FOIvd3cezWj1J8leawnDvQ8uWyA//DGf6/77IKzFcO38mzxWsEFYdXWJjyMA+p7qw3w5hfhDsxbHmfdhB/r/ABVVlc5kMs7/ABc5LB8MTPdY36BVyC3yXEeQyA5DI2CHsIoG8jQP5lVZlkPeRx+6wRRiE5ll4j/33fqvfFkHZ7v1WCKcGZbRZnHaaQfRxW1uRus+G5OPpIVFRRiDMs5ZHzSGSV7nvd3c47JUzD5P8LtOkdWhsxvaWSRyt2C0/wAj0UBFKHTHH4DMHmx1w46w7/5e0fcJ9A5VWUwWRxR/xdZwj8pW+8w/cKuVrjOIsljByQT88PnDKOZh+x/ogqkXT+Pw9m+liM4i2f8AMj96Jx+Y8lAynDd7GxifTbFR3w2IDzNI/ogp00p8dJkUYluP8Np7MHxOQ5ERe7UgZEP3iNuWvd49ucfdTfn2Yyh+DKBvw369eUrBS/xO5vfjH9AtzbUFv3bbAx57SsH8wmyk8RPzN1o6wrkUi1VfWcObTmu6tcOxUdZ2rNZxK0TExmBERQkREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAUinRtX5fCqQSTP1vTBvSjr6X/Z57EzBWJY+cWGk+O7XpsjX2QcFHiMhLdfTjqSusR/HGG9W/VbWcP5eRoczHzuaexDV3OVm/DeErWQqvc6xkHA+OejuV3QfTTf4qZhLbLeFo4+lk2V70UDS9nIHO7diCg+aT4nIV6xszVJWQhxYXkdAd60sMZXgtXo4bVltWF3xyuG9ABdxwvLaHEWVwuULZ2zBz3jXul2xsgfMFcXmaQx2XtVB1bFIWt+nl/BBZZfPRiscXhmGvj29HOHxzn1cf6Ln0RAREQEREBERAREQEREBERACuqF2xiKL3CZ49oHSEO90j1IVXTiE1uKN3Zzuqzvyma3IT2B5QPQBbUxWu/5M7fmnaucjJisvRNus11TIsLWurbLmy+W2qnnx1yu6Ns1eRhkOmAj4la8HCs7LtE4Jm1uH03o739l1gbFNk57Di6T2RvKGuHRriNnX20kU3RmZY6uv3dtsR4Pnk9OxWnbDNC5kjgCGkdTtbhiMhzub7JLzNbzEcvXS6TA1H2pn5q0wzySP1Ewddddb+y38QTT0c9QtsB8L9m4+R2eoUd3GMyie0Tu2R1/dylSyGtNayOaF3r3YfULRcrurTFhOx3a71CvOM6MdXIxzRNDRO0ucB+8O5VXY9/FVnu+Jri0H5K+N1ZrPWGlLxOLx4oCIi524iIgIiICIiAiIgIiICIiAiIgIiICIiAiIgIi90g8Rboq0037OJzvoFI/C5wP7x0Uf/W9aV0726QrN6x1lBRTvw0noyzXcfQPUeerLXdqVhb6HyKW071jMwResziGlERZrCLbXrzWpRFXifLIezWN2VfwcKSVgybNXK+Pi78j3be75BoQc5pdTwzkshjaNqtBipLAs/nJLQOmvRZT5vA0JwcVixMR/mSEtH2B2tcnGcknQ46sR6EkrKb6nhUiY8YXvgzZLgkYu0ww3IQBGCQebl7dvl0W+tnLleFvi4/HiyxgZ4njgEj59N/xVTiM/hrQLchUr1bDnajkEXMwDX5vPuo+ZtuxFrw7GDxrmv96OVse2yD1BVc6v+/8Aq26v6fqt+HK81XL281lJY3yTtIZ4R20kn1+2lwuUtPu5KzZk6Olkc4j069la/wDE0fKG/g+P5R2Hh9AqrJXvb7Al9ngrgNDQyFugr035/MiZiekYRERFogREQEREBERAREQEREBERBtqy+DZjkPZrtlbsjD4Vx+urXnmafUFRVPgljtQNrWHBj2/s5PT5FbUxauz5KW4nc3Yht6hfitsoTy8m/d5CN7Gu+vmuhw16xLlLYuU5oI7eiOZh0061revNVjchljPDUjhfJK7TW6cTzKZmb7sOYYDZM9zW52MeeWP0G/VREXrOJmPr/Cl66epHSfoq55Mlgrvs/iTeBG/ma0E8rm72psdufibLV9xmGtBp8g59jp5/XyUdvE8v5vEH3B/mFY4u/8Ai8r61dsJsFhcxs7AOcjy6d1H548YmPf/ADCZpSeeYnzx/aq4qyceQyIbCQ6KEcod6nzKrLdhsscMUQIZG3XXzPmtVgPFiQSM8N4ceZmtcp320joJBEJSwhhOgfVRutOfVNaVpERHg1IiKjQREQEREBERAREQEREBERAREQEREBERAXuka0vcGtGyewCsAyHHNBlAls+TPJn1V6U3c+CtrYaoMfJIzxJCIYv3n/0Wwz1K3SCLxn/vydv0UWexLZfzSvJPkPILVpX31r7EfFXbM+0kzZCzL0Mha391vQKMSSdk7TSaWdrWt1leKxHR4p1S308Cz78DunX8vzChaVjhmYsySSZaWVscY22KJvWQ+m/JTW81nMFqxaMS1txVua8ataF87+7eQdx6q5GBx2IAkz94GXv7HWPM8/U+S8t56b8Ok/CealXdJyljXbdrXT3u65pxLnEkkknZJU6lYieOkopOY5dDY4rmiiNfDVYsbXPnGNyO+rlQSyyTSGSV7nvPdzjslYIs1hERAXRYTLwTVfwfM+9Sf+ylPxV3eo+S51EFhmcTYw9wwWNOafejkb8MjfUKvXQ4nM1p6IxObDn1P8mYdXwH5fJUMrWtle2N3OwOIa7Wtj1QYIvdJpB4i90vEBERAREQERNIC9DSToDZ+Sk1qbpW+I8iOEd3u/otrrkcHuU4wP8A7jhslRnybV0uN15xDWzHTubzP5Ym+rzpZezVIz/eW+b5Mao0kkkruaR5cfmVgoxJv046Vz7/AOk3WOH5pz9gpFLGRZOy2vRfK6Zw2Glm/wDwqpdNZtxYHBw06D2uu3YxJZnYdlrT2YCpx6nexP8AjH1/lu8ZuOx0dXGjxLzHHxZXS/CR+VoB7Klnnj5ybdDTidlwcRtVocQdjopUWQnYOVxErP3X9VeNXUjxyrs0LdYmJ9GzmxrvyTt+hBWcMtGvMyaGSy2Rh5mkaBBWAjrXP2P9xL+44+6fooksT4nlkjS1w8irxrf9Y+Sl+zzXmJ4dbF4PEr5rMHgHKNA1BI3l8UDzB3olcxfktGw6O21zHsOiwjXL9lHjkfFI2SN7mPadhzTogroTxBUylQw56q6WZjdR24ABIPQH1UTqWmMeCkUiOXOIiaWawi90vNICL3S8QEREBERAREQEREBERAREQEREFhU1UqG2QPEd7sXy9SoLnFzi5xJJ7kqbcHNQqOb8AaWn5FQFtq8Yr4M6c5lPwtEZHIxwOe1rT1ds62B3A+a7DJ4atYlq0oa0EUfNzvezo8NA7dvmPNcVjZWQZCvLKeVjJA5x15bXX1ctUtcVtkryc8clbwg7lI97m3rqmntxiXN2jfuzXwiVfcpxZPNewVIY4KlTpLI1oHbvs/wU3PMp4qvQsVqkLmc+iCwHnbrzUOa/bweSyEIptmZPKZNuadEHr/VbM/m61/Fx1KoEk8haHN8MgsPTtsevRTmMT5q4vNq/pQ+KcVDWEN+m0Ngn7tHYHW+i51dfxVIyrg6WPJBlAaSPQAaXILPUiItw6OzzM6fKfT97HXGHsA1w/VQFPq+5jLbz+blaP1UBW1PZr7v3aV6yIiLJcREQERSa1Qz7e4hkTfieeyZwtWs2nENDWuc4BrSSfIK1x2Nd4wfZYOUdmE9So77jIGmOm3lHnIfiK9xlpkNt0liQ6LSNnZWdt2OHXoxpV1Ii05+yzfSgfY8ZzWBkQ6tA6fdY1PZJ5X+G2ORxO9eHrQWFGVliO5Ex3V7nOb8wVFx7qkOjNI+KZjjvW+o9Cs8TiXd3lYmsxEYnKb7NAy65obF4bxpzD3B9QqrIU3Vp3crSYu4dpS5ZW38tB4IJa3W3a9Oqyyd98VzkiILWjTmnqCVau6Jhjrd1elp6RE8TCmRWBigutJgAimHUx76O+iguBaSCCCPIrWJy86+nNeesMURFLM0pteuyOL2i1sM/KzzesaMDZHukl/ZRjmd8/ktdqw6xKXHoOzW+gVZ54b0iKV32+D2zafYd191g+Fo7Bao2+JI1gIHMQNlYL0K2GU2m05s6GanHDRbHHFG57tN5j32fNRbhrUTDB4LXge88kdStj70L/YxGS4xkcwDT06aXmShacjHJK1zoXN0S0b0ueuc8vW1dk1mdPHGIbbcUX4cZn12QyN6tA0foo1uCO1jm3ImBj2j32tGgtti5WioPgjkfI5w0ObewvGf4bAkSdDJvQ+qRmI+JfZe0xxjbz71IiIuh470HSnwyNvRivMf70fs3/wBCq9ZNcWuDgdEdQomMtNPU2T6eI9pY8tcNEHRCxU6+BKyK00ftBp3/AFBQSkTmDUpsthtrRGezFCHBpkcG7d2GzpfTrXD9Whw0KtepUmsyMEZlf8Rc7pzA69T8l8sC7+3xNi3V8E2KfnfVlYZW8jhygN0epClm9yrMJw6+hi7FWOWMgy2ZSzb3aB0N/Nw/gpNlmHy3CU+Tr46OoYNmN3I0Hbe31B7aULjilBNxDStXLHg0Jog0zNaXdtnQ167U27mOErWJZjvbZGVox7sccb27I7b91BW5XG1M3wqzN0q8dezC3UzIxytOu/T+K4hfQaGsR/ZvZNn3XXOfw2nueYco/gNr58gIiICIiAiIgIiICIiAiIgIs42OkcGsaXE+QUsY/kANmaOL5E7KiZiGlNK1+kNdS34LTHI3xIXfE0/zC3OoNmBkpSCQebD0cFh4VAd7Eh+jFkyGmXAxW3sd5czVpGrGNtozBPZrZzW0Z98LehkjTpMY2GjXewac58fNI7591Ik4huRxNmdZmETjprm12hp+hISvRFetK7MOfK4MDoIRH7z/AJ7Pkq/JZkZNscV8TsbENNYzQa37K0U0J9mIz65c19C9ZzeJT5+KrsHK2UWGuLQRzxtBcD59lqHGM+vej5/m4N6fwXrc3StY0UMiXWmNGoZJBqSL/uHkoeQwUeMZFLZleYphtj4xzNd91bu48q/Rnsp5T9UHJ3WX5TMWv8Vx95znb6eihvjfG7le0tPoQpotVK/WtXLn+T5DvX2UOWV8shke4lx81Gpjrnn0a0zHERwmXf8AD1Iav5vjk+p8lXrN73SOLnkuce5KwVL23TwtWuIERFRYQIvWAucGjuegQSalYTEvkPLEzq4/0S3aM2mMHJC34WhbL7hDGypH2Z1efVygqsc8ujUnu47uPiK2wmUdj/FAMLQ/R3JFznp6KpUzFY6fK346lce889XeTR5kqbRFoxLCMZ5jLq6uYv2qti1Xk1BWG5H+C0AfL5lRf+J3uaXuLHN3oudXBG1D4jyUDIY8LjD/AIKsffeP86TzcVEw/EFnFxur8kdinIdyV5Wgtcsu4p5L76/oj/fit4uJKIcXS1KriRolsJaT91BylrD3K4bWgZVlDuYvaCebp26qTNhaObhda4edyzNG5KMh94f9J8wuZex0byx7S1zTogjRBUxpVicwnvI/TH1/ka4scHNOiOxU6cC7W9oaNSx9JAPMeqr1IpT+BYa4/Aejh8lpPmnStHs26T/uWheLfch8Cw9g7dx9FoUwztWaziU6Q+Fi4mDoZXFzvsoKnXPep1Hjtylv6KCq1aa3WI9I+wvQvF61pc4BoJJOgB5qzFNhuXJHRwQdXEhrWsb1JW25YyNCd9SyeSZhHMDokdNq5Y2PhGg2V7WPzVhu2NPX2Zp8/wDqXLSyvmldJK4ve87c49yVG2Gvf6n6pXWD9oy1/wBjdajie5hMfOwEPcOzfuoti7K2V0F2qwvjJaWkaIKro5HxSNkjcWvadtcO4K6q3Cziyh7dUa1uWgb/AImEf5zR+dvzUbYWjtGr03OVcQXEgaG+3osV6QQdEaIXiswEREE6H+9xczD3jcHhQSpuO6tst8jEVCKrHWW+pzSs+n7iIiswWTs5efiPwyR7ZKwO2h7dlv0Kr438kjXgA8pB04bBWKILHLZu9mHxm3IC2MaYxo01v2VciICIiAiIgIiICIiAiIgKRVqusOPUNY3q5x7BeVa7rEoa3oO7nHsAttuw3lFev0hb/wDsfUqJnwhtSkRG+/T7s5LbIWmKmOUecn5nKESSdkkk+qt8RWhdDJNJyPI8nflXtlkNOuJDE175nb7dAPQKm6InEOm2he9I1LTiPspl0WLdi8Lj48lOY7uQk2YK/dsWj8TvmtViOL8O9o9nY1405oaN/qomSrxmvFbhaGtkHvNHYFTF8s9TstqRM5zxn4I13I2r1x9uxM90zvzb1r5D0C2MuMmHJcZzjyeB7wUFFaYywpqWp0SbVUwae088TvheFZYXONqQvoZGI2sbL8UXmw/vN9Cq6na8MmKX3oH9HN9PmvZqgitMjLwI5COWQ9tHzSPKVr1ia76dPs0TeH4z/B5vC5jyc3fXlv5rBfUncOY1uGq4+BlZ0lgAGfXvuHQlzT9FVWr+Ex2afQbh2TmvyQwtDQS5x+Iknue38VLFwS8X0q/XxFPimvQNKuYr8WpWco2x35SPTa4jiHGfg+ZsUwSWMO2E+bSNhBWIiICl4xgfcaXfCwFx+yiKbiyDYczzexzQot0a6HOpX3o0zzJK95/MdrWvpOLw2OpcKGfkqWrEwOny9i49Aweh30+qiZIYXhl9THWKLLOojNK4t257uzRvyGwVLOZzOZcCr+LKVcXw97Pj3E37exYl1oxt/dB+a6XNPxlKpicsMbBDJO8CSBzB1jI67Hy6dVz/ABrhYcTkY5Kg5a1ppexv7p8x9OoRDm0REGyCeWtMyaCR0cjDtrmnRCtczmIcxWhklqhmQadSzM6CRuumx6qLg6UWQy9arPK2KOR+i4+fy+/ZfSbnD2LsX68ArV2QVW+LI1g04+QDvkep+yD5Qi7nhX2LN8TXpJKVfwPD/uo/DGmgHp09Vq4eq0sz+JYWxBG2RjnPrzNaA5vXWt+YHT9UHMZD3oash7uj0fsoKsMrG6Dwa7/jiZp312q9Vr0bdo/5J+H2T4f8RjpIvzxHnb9PNQFvqzmvO2QdR2I9Qu14MweOsT2Ls3hTtA/u4njfKPU/ySOJTb89ItHWOJ/Zwa6Dhw08dWsZi0WSTQHkrVyerpCPiI9AukyNbGYjHzZWSrBK+7MGRhrQWMZ6tHzAJ+6yH4NkuF7t2DFx1GVSfAkc0bcR2Pz69NKzB8/t2ZrlqSzYeXyyO5nOK0rsOIMfUv8ADVXP04WQPOmTxsGmk71sD6/zXHoC30rc9G0yzVkdHKw7DgtCyYA57Wk6BOtnyQS8rfOTvOtugihe8DmEY0CfM/dQl9OPD+Oh4dr1IGVZZ7XKwTke88nu5v0Gz9lTZaOhBxRjMJVqxCCCWMSuLdukJ10J8+hQ9XFIu7yHsON46bUdSgNOzGyN8fhjQJ6bHoue4owzcPm31YduieA+LffR8v4FBDojkrWpT2DOX9VBKn29VqsdUH3j78n19FAVY82+txinkIiKzAREQEREBERAREQEREBERAWTGF7w1o2SdALFT6YFau+274vhjHz9VEzhpp032xPQtPFSD2WI+8esrh5n0UEbJAHmjiXEknZK8SIwal98+i5qM9jgmjmkiaZB+/1C3yCGzBE7xmuFfRdob39lV4vHWcteZVrN293Uk9mjzJ+SxuVmVchJWZZZKxj+XxWj3T81SaZ5dNe1xWu3bwtXz1Ja7q1eRrPEPk0la7vgNpNqGdodGN9t7K05nCzYnwpRKyxVnHNFYj+F3y+RVXtI08Jt2zdE5rHl8HhREWjhAp8B9qpPgPV8fvs+nmFAUijIYrcTv+bR+hUS10bYtiek8Osr8ZxCxiA6u6NlMckri7ewWgbA/ipGQs08BxJJl31vbo7Y8StIyQcrf3vv/quKuR+FakZ5B3RaS4kaJ6BT6qWrtmay+gUr9TiTNQXmUW0203Gaew9494a6Df8AvsuV4oybctnrNqL9lsNZ8wBrf9VUhxAIBOivEVEREBZwyGKVsje7TtYIiYnE5h19niFsXD9arFWJDZmzCTm6bDubRCsOIJqNizR4l8E3KgjDJImvA5Xg7HN+p/guLqWWsDoZhuF/f/lPqvLVZ9fXvc0TurXDsVWOOG2pWLx3lfj6f06+3mq3F8kdCLF+HYcRqdzwfCYCCfL0UDj3KQXsjBVquD46bCwvHYuOt/yXLgkdiQsVZgIiIN9GwKt6vYLeYRSNfr10dru8RxbVyHEkxnj9mitwNhBe7enDfn89r56iDqcZdPBmetx2K7p/d5W8rgNjewVN4ULKLMjxDacIYnNcyEE9XEnfQefkFxRJcep2vdnl1vp6IN12ybVl8p37x6bUdETota02nMit8JlxixKSJC9wHI5jtcvrsee1UJtCtprOYd3Ymq5rhSvVjeXTUi1wYDoyNHQgfPSxHGGMmox4xuDL4RpscReCN+Xl3XFwzyQP5onFpUoT1bP7dhhk/fZ2/RV5hril+k4n6Omz80eH4Pq4Iva+3JqSUA75OvN/PQXFKc/HyvHPDI2cf8p6/ooskMkZ1IxzfqFMTEqW0r06w1omkUs3WR8XRthw0Pszm+wPbzuLt8w5eU6H3W7icMp8R1OIa5FipM9kgLXfmbrp8ugXHLY2OV4Aax7h8gmUxEzxDq4Jv+K+MIrrIjXghDXyFzt8ob17/Na+LMrWt5h1yFzZC1gjh11Ghv3v4lUEePsaJk1CzzLjpRZAGSOa1weAejh5qs4nhtEW0vzTHuePc57y5x2T1JWKIrMBERAREQEREBERAREQEREBERACnZA8kVaEdmxh33KghX9bB3c8InUWMdyRAPLngAaVZ6w20/8Ajv8AD7qBZRRvlkbHG0ue4gNaO5KtoOGMpPXfMyAcrZPCG3AF7t6031XQYTh25gpX3r0DPaOUMqgvBY2R3Qcx8v8A1VmKDkZWcM4v8KrOByNhoNyVp+AeTAVyqnZipep5KWPItcLJPM4k75t+YKgoL7AZeGOF+KygMmOsHv5wu/eChZvDz4e54UhD4njmhlb8MjfULPD8P5HNB7qUQcyPo57nBoB9FOmr5l/DDo7IjbQrTHkdIRzb7ab6jaDnUVxJwzkYX02zNijFzpE50g0TrfX07qDkcfZxlt1W3EY5W+XkR6j5IIqyZvnbrvtYqTQi8W2zfwtPM4/IKJWpWbWiIZ5X/wB/k+38lDW61J41iST94rSkcQtq2i15mPMREUsxERAREQFJrXHQgscBJEe7HdlGRJjK1bTWcwnuqRWRz03jfnG46I+iiSQyRHUjC0/MLAEg7B0VKjyNhg5S8Pb6PG1XmGudO/XifToiIppvRP8A2lOI/TontNPzp/o8pmfJHd08L/dCRTfaaY7U/wBXlPbYG/BSi+52mZ8ju6eN4+v8Iscb5HcrGlx9AFItV2V4WNcdznq4A9AF6/JTFpawMiB/cbpRHOLupJJ+ack93WMV5l4iIrMRERAREQZNcWnbSQfUKSzI2WDXicw9HDaiIomIleupavszhN/Ed/HWgd/26T29nlThH22oSKNsL9/qeab+JSj4IoW/RiwfkbT/APNIH/L0UVFO2CdfUn/Jm+R7zt7nOPzKwRFLKZz1EREQIiICIiAiIgIiICIiAiIgIiIAXecMP/8AZaW4xscb6TnNf06SsPU836/wXBrdHbsRQvgjnlZE/wCJjXkNd9R5pjMLVtNZzDs+J8hO78Ir4lksb4d6YG+81/QD+ZVnlqGTqcDvqvc6zOQZZ5Hv+AA8x1vv2XMR8UB+GZWsQuNuvoQWGHR0PJy0R5kWZGi5ZuCMn+8jE7i148wq8w02VvzWcek/yu+NgJ+G8NcnGrbmAO9SC3Z/jr9Vwy6XiO5Zz1pksPh+zxN5YomO+Ef6qgfWnj+OJ4+ymJiVbaV6xzD6BwpfEXA1yTwIv8M5wOx8fQHZ/X+Chf2ikwwYupEOWuIyQB230H+/quMZbsxQPgjnlZE/4o2vIa76hXVriGPI8PR4+/A99mv+wnafL0cplmvOOyRgsKR0Ib//AC1YccAT8P4W5ONW3sAd6kFoJ/j/ADXK173iWYPxOSxYqxHfh+IT09BvspXEWcmz15rxH4cMQ5YYh15R/qhCnHdT3/4KmWH9vMOv/K1R2VLLj7sL/wBFvdQsvJfO9jPUveqzMOnSpeImYrOUFCCNbB6qb4FOHrLYMh/djH9Vrt2hO1kbIwyNnwjeypzlSdLbGbTz80VERSxEREBERAREQEREBERARFkxrnuDWglxOgB5oMUU+3iLtKBs1iAtYfPe9fVQFETE8wmYmOoiKwp40WcdatmcR+z690t3zb+aTMR1IjPRjDj/ABcVYu+KB4Lg3k18W1BV5jI3z8PZCGJjnyc8ZDWjZPUKmljfFI5kjSx7TotcNEKKzmZha0YiJYIiKygiIg9A2UI19FJrPqNqztnje6VwHhua7XKfn6hR3O30A0B2CDFERAREQEREBERAREQEREBERAREQEREBERAREQEREHoJB2DoqQy9Zj+GZ33O1GRMZWre1fZnCaMnY/NyO+rV7+JP84YT/2KCirthp3+p+pO/E5h8McTfoxYnJ2vJ4b9AFDRNsH4jV/VLe65Yf8AFM/9VpJJ6leIrM7Wm3WRERFRERAREQEREBERAREQEREG6o2J9mJs7i2IuAcR3AXRGmzh9tu5oPfzeHV5vmN7/RcwFc5nJMuYvHxNl5pI2kSDXYgAD+qyvEzMR4NaTERM+LZgrElye3UsPLxajcSXdfeA6FQaGKmviVzZIo2RHT3SO0AvMNdjx98WJWvcGtcAG+pGlCe7mcXep2p2zFpwjdG2MrSKrjquREdy02evyb5odkc3oVb4vJwyw3YqVGKIsj8RjT73Pr1XJLOOWSJ3NG9zDrW2nXRRbT3RzKa6m2eIXOOzvs816aVmpLDPd8MaDXDssrThl8KbjwPa6pDZD++09iqFZB72tc0OcGu7gHoVPdxnMdUd5OMT0YlERaMxERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERAREQEREBERB//Z\n",
"text/html": [
"\n",
" \n",
" "
],
"text/plain": [
""
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from IPython.display import YouTubeVideo\n",
"YouTubeVideo('e0CAbRVYAWg')"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(832040, 1346269, 2178309)"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Let's create a function for the famous Fibonacci sequence, using the \"naive recursive\" approach.\n",
"## You'll notice how slow this process is.\n",
"\n",
"def fib(n):\n",
" if n<=2: return 1\n",
" else: return fib(n-1)+fib(n-2)\n",
"\n",
"fib(30),fib(31),fib(32)"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(832040, 1346269, 2178309, 354224848179261915075)"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Now here is how to code Fibonacci, using Dynamic Programming. Look how fast this program runs!\n",
"\n",
"def fib(n): \n",
" myset = [0]*(n+1) \n",
" myset[1]=1\n",
" myset[2]=1\n",
" for k in range(3,n+1):\n",
" myset[k]=myset[k-1]+myset[k-2]\n",
" return myset[n]\n",
"\n",
"fib(30),fib(31),fib(32),fib(100)\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"scrolled": true
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Step 0 -> [0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
"Step 1 -> [0, 1, 0, 0, 0, 0, 0, 0, 0]\n",
"Step 2 -> [0, 1, 1, 0, 0, 0, 0, 0, 0]\n",
"Step 3 -> [0, 1, 1, 2, 0, 0, 0, 0, 0]\n",
"Step 4 -> [0, 1, 1, 2, 3, 0, 0, 0, 0]\n",
"Step 5 -> [0, 1, 1, 2, 3, 5, 0, 0, 0]\n",
"Step 6 -> [0, 1, 1, 2, 3, 5, 8, 0, 0]\n",
"Step 7 -> [0, 1, 1, 2, 3, 5, 8, 13, 0]\n",
"Step 8 -> [0, 1, 1, 2, 3, 5, 8, 13, 21]\n"
]
},
{
"data": {
"text/plain": [
"21"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Why does this code work? Let's add a \"print\" statement so we see exactly what is going on in each step.\n",
"## Can you figure it out? And why is this better than our first \"naive recursion\" approach?\n",
"\n",
"def fib(n):\n",
" myset = [0]*(n+1) \n",
" print(\"Step 0 ->\", myset)\n",
" myset[1]=1\n",
" print(\"Step 1 ->\", myset)\n",
" myset[2]=1\n",
" print(\"Step 2 ->\", myset)\n",
" for k in range(3,n+1):\n",
" myset[k]=myset[k-1]+myset[k-2]\n",
" print(\"Step\" , k , \"->\", myset)\n",
" return myset[n]\n",
"\n",
"fib(8)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# The Knapsack Problem\n",
"\n",
"## Let's solve one of the hardest problems in Computer Science with dynamic programming."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/jpeg": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEABALDA4MChAODQ4SERATGCgaGBYWGDEjJR0oOjM9PDkzODdASFxOQERXRTc4UG1RV19iZ2hnPk1xeXBkeFxlZ2MBERISGBUYLxoaL2NCOEJjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY2NjY//AABEIAWgB4AMBIgACEQEDEQH/xAAbAAEAAwEBAQEAAAAAAAAAAAAABAUGAwECB//EAE0QAAEEAgADAwUKCwcDAwUBAAABAgMEBREGEiETMVEUIkFhcRUyUlSBkZKhwdEWIzM1QnOUsbLi8DRDcnSCk+EkVmJEU7M2RVXS8Qf/xAAZAQEBAQEBAQAAAAAAAAAAAAAAAQIDBAX/xAAtEQEBAAIBAwIFAwQDAQAAAAAAAQIRAxIhMRNBIjJRUqFhkfAEccHRgbHhYv/aAAwDAQACEQMRAD8A/PwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACXjKLslejqsejHP35y9yaTf2Fk32S2SbqIC4zHD9rExtkeqSxO6K9qL5q+s643hmfIY9LjbEbGrvzVRd9C9F3pj1sOnq32UQPVQIZdHgLXJYSXH46vbfKx7Z9ea3vTabKotmvLOOUym4AAjQAavEcDWsrjIbrLkMbZUVUarVVU0qp9gGUBrcjwBkadR88U0VnkTasYio7Xq8TJaAAAAAAAAAAaLufhueDhyPMrPGsb1T8WneiKugKQAAAAABoOH+ErucgWwyRkECLpHv68y+pDrnuDLmFpLbdPFNC1UR3LtFTfqAzQB1rQrYsxQtXSyPRiKvo2ugOQL/iPhafh+GGWWxHMkrlaiMRU10KAAD1rVc5GtRVVV0iJ6SXksZZxcscVtnJJJGkiN31RF33+voBDBd5vhufDUatqWeKRthPet729N/KUgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAueE//AKhrf6v4VKYsMFdix+VhtTI5WM3vl7+qKhrC6ylY5JbhZH6NYlrSzLQn5VWVnNyO/STuOVOizHY19aNVcxOdWqvoReujGcQZqO/er2aXaRrC3orui72W9fjGs+kjbcUvb8qoqsRNL6+89M5Md18u/wBNyTCa9/MRuG2w+Q7hx3ldrnXmc5NNano6r9hP4qx9ZcKtrydkU7OVdsTxXSp6+8rsFxDSqYlaVpkrffedH+ki/uUk2uJMTPiXVFgmVvJyMYqd2u7rv2GN49Gtu2WPJ6vVJfKZnUr0sVUseTxKkcjNorUXp6UOl/BVchPRswRxtiR23o1ERHN1tP69ZR53iCrkcSyrCyVHorV85E10+U6YXimGji0r2WSPkj2katRNKnoRS9eNyu/DM4uWccs891ytChezL4krxLHTanMjWoiOc7x9iJ9ZJXGwW0lr2cfFHEnSNzVTevsMZhs/Jj8hNYmasrbC7kTfXfihczZ7AvmWytaZ8q9Vb3Iq+zehM8bEz4eWZam9fz9WStw+T3J4N77ORzN+Ol0frHCbWu4Mqtc/kasT0V3gnMvU/JbEiS2JZGt5Ue9XInhtTbYjjHH0eGY8dLHOszYns21qa2qr6/Wee+H057ba6nEzDYB7o5przI2ukRyu5nOTwQzvA+CpyYlcpNWZYnlc7kY5E03S60m/WVvCfGFfE411O+yV7Wu3GrERdIvenVTpheMqOMls1Fryuxz5FfDpE5mIve1U8CK0GZwEOVwkr56MNO6xquasaoutetE6ofNqLDcH4iJ8lJJlcqMV3Iiue7W+qr8pQZHiHh5lKwzHVbDrErVRrnqumKvpTa9PkJdXjbFXscyvm6jnPaic3mI9rlT0+oCy4bXEZq1es1qMTYvMTlfEnRdLsgcE0qs2TzbZa8T2xz6ajmIvKm3dxHocY4qjmZ3wVHw0ZY2NRGMRFRzd9dJ47+omwccYCpLMlanMxsjudz2RonO5e9V6gSeFcdSmjyiS1YXI29K1OZiLpPA5tu8LXJ6+MjigVGTcmnR67kX0+napr1lVg+MMfj48g2aOdVsWZJmcrU7nd2+pl8Hbp08oybIV/KK+nI6PSL3pr0gfo/FFOKPFWkZiIZYUgdySRonNG7XRda7vWikOzBBB/wD59XsJXiV8cEUibanV3QjT8a4iriZK2NisPe5qoxsm9N361Xu9RXWuK6M3B7MS2OfyhsDI9q1OXaa9YGgyGDpcR4ihZowxQ8z2PcrGoi8q++Tp/XQ7XMVi7uYr4xtWFrK7O3lRjURV9DWr6uqr8hmOEOL4MNj5Kl1kr2I7mi7NEXW+9O/xK6lxRYrcTTZZWLI2Zyo+Pf6HoT5NIB+j+5daaSSnLiKzaSN016a2q+zXQ/KeIKDMZnLVONVVkb/N34KiKn7zaT8S8OXZEtS07j59dWtaqb9ul0pjco2bI5SexWozRxyO21iMXohNq1/BHENKHEsxl5/k7kV3Zvd0a9FXx8dqffEvD1qDGSe596WSlK9vPBK7n5duTStX5jjw5bjhw0OOymCtTJG5ytetfmTqqr6e7vJ3EOQv28WtDEYm0xrkRvO5qN5Wproib9RLnjPdI724sNwfiYXvopMr3IxXcqK5y62qqqkXibB0WtoZWlC2F/lEXMjE0jkc5PR4k+tblyOPjgzeEmc9mlXo1zVVPT39CJn35fJy1YauNfHUhmbI9XyMRzuVe5E2ZvLh90NLDiOJk2VwccrGvY6w7bXJtF8xSmz9GrHxphomVomxvReZqMREd1XvLPNeV3bOOsVoEiWpN2jknkam01rSaVSwnt4tZ4rc61kniTTXyPbtiL36Unrcf1XVQbNbG1uLMfH5CztZInLG5qIiNVOu1T0r4FdxzmaNV01Cagktiav5k2k83e0T19NHXKZjCuzNPIrlGc1Vrk7ONvPzb9aEbJ8UcM3kes0L5ZHxrF2iQ+c1q+Cr7R6s9pf2E7izEV7dPG1o42RLJZZHzNb1a1UXejpekwnDK0qfue13lK8iKjEVfQm1Ve/vQq7/ABjhb7IGvW5GsEiSMcxid6fKT3cVcNZGSJ1lWq+FeZizRL5q+ovqz6X9k09t8OY+txNjbMNeNscznski5fNVeRVRdfIS3S4atxEzGNx8flM8fMr0jTSJ6E+ooMrxfWbxRUka7taNVrl3F1VznNVPT4bK+fiilJxlDl2xzeTsi5FTlTm3pfX6zpLuSiHx3j6+O4gVlWNI45Ymycre5FVVTp8xmy+4wzFfOZZlqq2RsbYUYqSIiLtFVftKEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAu8bgYr9Btl2UqV3K5U7OV2lTRI/BaJf8A75jvpqZwHO45b7ZK0n4Kx/8A5zHf7inn4Lw+nO476amcBOnP7vwNF+DVVO/P49P9Sj8HKPp4hofOZ0E6M/u/EGj/AAdx/wD3FRPfwfxSd/EdX5GKv2mbA6M/u/EGi9w8MnfxFD8kSj3Ewn/cMX+y4zoL0Zfd/wBDRe4uE/7hi/2XD3Gwad/ELPkhcZ0Doy+6/j/Q0aYrh1Pf51y/4YFHkHC7e/L2neyH/gzgHp37r+P9DRrFwmxP7TkZPYxEPO04Tb/c5J/yt+8zoE4v/qjRdvwn8UyX0m/eOfhNf7rJJ6vN+8zoL6f639xo0scJsT+xZCRfW9E+0LleHYusOCfIqf8AuzKZwE9KfW/uNH+EtNi7h4foN/xN5vsPE4vtR/2ehj4f8MBnQPRw+htoXcZ5dfevhZ/hhQ5P4uzb/wD1qt/wsan2FGC+jx/bEWknEeZk99kbCf4X8v7jg7L5N3fkba+2d33kIGujH6CSuRvO77lhfbK77z5dctO99ZmX2yKcAXUHrnOcu3Kqr61PACgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHoHgPpsb3rpjVcvqTYcxzF05qtXwVNA0+QAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEzF1Yrc8iTve2OOJ8q8iIqrypvXU66w3w7/0WfeML+Uuf5SX+E2uMw2O4iw2Msw14YpIZUSwjGonNrvRfb0+cDFaw3w7/ANFn3jlw3w7/ANFn3n6PJwzivdVuTSGDyJkDuaNGpy8yL369myjj4KjyrEv+UeTeWbkhijh22Nq9Woq78NAZTlw3w7/0WfeNYb4d/wCiz7zVpwo21g8bVRYYrK2ZWSzIzzlRFf6+vvSVieDKNK9Wnls+VxyOcxIpYNIqoi9eq+oDFaw3w7/0WfedK8GHsWYoGyXkdI9GIqsZ02uvE01/gylJK61XyLWxOtdk9qR9GbdrlT1ptEI2fxGNxWfoMpT6kSaJrq/L71Onnb9OwKGaHDwzPidJeVWOVqqjWej5T41hvh3/AKLPvI1/84Wf1rv3qaXgOlVuPyKWq8cyMg23nbvSgUesN8O/9Fn3nZlXEPpy2Uku8sb2sVOVm15t+v8A8SpUn1/zDd/Xw/ueB7rDfDv/AEWfeNYb4d/6LPvIUCxtnjWVFdGjkVyJ6U31NzlGYm9wZNfjxjKKtk5a6oicz+qdfl6/MBk9Yb4d/wCiz7ztaq4iq9jXyXl542SJprO5zUVPT6yoLDM/2iv/AJWD/wCNoHusN8O/9Fn3jWG+Hf8Aos+8m8J4L3XuukmRfJK/nS6Tau8Gp7SXx/j4aOXi8lrNghdEmuRukVdrv7AK6rUxFp8jWSXk5I3yLtrO5qb8fUcNYb4d/wCiz7xhfy9n/KTfwKVwFjy4b4d/6LPvGsN8O/8ARZ95r+G2YbJYWeKXFsjirQN7W2/W3P110vo+cwCgWz6uIZThsrJd5ZXOaicrNpy69frJNTH4h1N9+SS0kEbuXlejU518E0V9n8xUf1037mF/g2QTUcQ2drHQNtOSZH+97l1sxnvtJ7t4e9+ji7iGixnZ1EsVGJ3JHCzfzqp3hkpcQVJK8r53SQ6ckr2NR2t+o7cdUooKUEtXHVIq7pfNsQO2rui9FTSfvXuKzhVvZR27L+jfMiT1qrkMZYY4zcndvHPLK6t7KK3Cle3NCi7SN7mb8dLo4krKfnW3+uf/ABKRTs4gAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAs8Ex0k9pjGq5zqkqIiJtVXlLPBZLM4OtahgoTPSdOnMx3mO1raf16CrwblbNbc1VRUqSqip6PNONOSzatxQeWPj7R6N5nPXSb8QLuLKZqPh6TEeQzqx6r+NVjuZGqvVCZQ4hzFXHQ05sMtlsCcsbnxuRURO4jO4YzLc2zGeVqrnRdr2vO7l5f/AO/vKq5TylazPEySxOyFytdLFzK1VTv6ganC5a3Zt04MlTkrQwTPnSVsburl5ui+CecpaZ3JrWWverQvs3Y3qjYo1e6PlVFTa9E0pipMVlGYWrkmWZJWWXqxsbHOV3Tf/wCqlarsgkbnq60jGryucqu0i+CgaBczmfIZazcZI3tLPlPP2bto7mR2vqO93K5HNXKKT4hYFZYje+Vsa7XS66rru6mal90oY0kl8rjYvc53MiKfeLtWHZWmizyqizsRUV6/CQD6u42869Yc2nOqLI5UVI18SfgbWUwbrCxY2WTt2ci80buhV3rVhL9hEnlREldpEeviXGDwORzVGS3FkUhjZJ2a9pI5OukX7QKVcZf+JWP9tSdBjrqYS2xak3M6aJUTs12vR5EvLbpXJqz7b3uicrVcyRVRfYd4LNhcHccs8m0mi0vOvTo8CPFjrrJWOdQne1rkVWrG7Tk8DU2+JMpaxz6S4FrY1jWNuo3LyIqa6GRjsWpJGxtsS7cqIm5FNBk+G8rjsY697oNnjjXUiRSqqsAovcu/8Ssf7ak7LY66+eBWVJ3arQouo170Ymys8rs/GJfpqT8xasNsQcs8qbqwr0ev/ttA+8a/OYxy+SRW4muVFc1rFRHa8SVxBcy+esRyT0J42xt01jWOVE9ZHwGPyGdtSV6910bo2c6q97ta2ifafOcpXcLZZDJf7ZXt5kdFKqp3gfWIx91k1hX1Jm7qyom416qrFIHuZf8AiVj/AG1JeHszums808i6qzKm3r38ilf5XZ+MS/TUDXY7iHJY/HR0YsAixNTruN3nL4qZqxQvzTyS+QTt53K7lSNdJte4u6fDOWu4tLkGQY5yx9okKSrza+wznldn4xL9NQLKxjrq4WmxKkyubLKqpyLtNowseFp7mLsOjsUZ1gkXe3RKqNXu3oqp7Fj3FpKk0vMs0qdHLtejC2xWIe+xBDeuTeUT9WV2yKiomt7cvoMZ2a1XTCXe4uMtVvZpkVOVkFWhF57OwTqq+jovd0VSllgs15KmNrVZlhisNfJMjF1Iu+/5PsLXLYaGn2EcrpIm2F5Ip4rDnJzehFRTKxPt1s1FWlnlVWTta5OddL5xzw3cviby1MfhRcp+dbf65/8AEpFJWU/Otz9e/wDiUindwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAaVfQep3mqjZX4VoxzzxMmy87eZjH9WwN8V9ZjPPp/uKNmEykkfaMx1pWeKRKQXNcxytcioqdFRU7i1k4kzEk3arfmR3oRF0nzdxZZdjM5hEzDI0ZcgVGWmtT3yeh/9fYZ6ssbOr3VlweqioiKqd54dUAAAAAFjhfylz/Jy/wlcneS8dbbTme6SJZGSRujc1Hcq6VNd518oxfxGf8AaP5QN9BxTVThRL75YlyEcSxcqqnMru7u8O5SRw5k6UeIpLPlIFc6Llex8rW8q+z0r61PznyjF/EZ/wBo/lHlGL+Iz/tH8oH6DTyeMpw4yFchUXs7UvNyyppqL2ml9SdU+cS3cRj8dNHLkKtjnvJO5jHoqoiyIvdvro/PvKMX8Qn/AGj+UeUYv4jP+0fygfofEuVx8+DvMbbpzMlj3Gnborub1N0fm+L/ADtT/Xs/iQ6+UYv4hP8AtH8p9wXcbBPHMyhNzRuRybselF38ECJf/OFn9a796m34JsVIMQkc+QothfI588E+ubuREVNr3dE9BkpbeNllfI6jNzPcrl1Y9K/6T58oxfxCf9o/lA8zbqrsxbdR0lZZF7Pl7teo9r/mG7+vh/c8eUYv4hP+0fynVuQxzKsldKE3JI5rl/6jrtN6/R9agV0DWPnjbI/kY5yI53gm+8/QcrYx1XgqaguRqTu6JD5M5EV+lTXMm+/xMV2+L+Iz/tH8o8oxfxGf9o/lArywzP8AaK/+Vg/+No7fF/EZ/wBo/lOtnIY6y9rpKE22xtjTVj0NRET9H1AWfA07a9yzIl2tVlWNGt8p969FXqnenXoh8cdy42XLxrjVhd+L1KsOuVXb9XQqvKMX8Qn/AGj+UeUYv4hP+0fyge4X8vZ/yk38Clcha1shj6znujoTbfG6Nd2PQ5NL+icvKMX8Rn/aP5QNvwvPjsZgXrPkqfJLFzORrkbK1yp1avXrr0H5yutrruJ/lGL+Iz/tH8o7fF/EZ/2j+UCwxKRK3DpNrk8pl7/HTNfXo4SQWLPEckdqy2o9z15pZX8qNb7fYfDshj3VooPIZkbE5zmqljrtdb/R9SE1/EdaaBsVnHrYRvc6WRFVPl5TnlLMuqd3TGy49N7NPlK1K5Tx1bH5StJXoOa5zGPRzl16VVF6f8mJlstt8SpO33r7LeX2bRELWzIyjjEkZi7UFK4iLzJMic31KqJ+8qYrmNhmZKyhNzMcjk3Y9Kf6Rj8V6zKyY9MRsp+dbn69/wDEpFOtqbyi1LOqcqyPV+vDa7OR0cwAAAAAAAAAAAAAAAAAAAAAAAAAAAABbcLVWW+IacUibZz86/6UVfsNG6zj+LZVrX5m1bUM6pDIn95Gq+99pnOF7cdLiCpNM7lj5la5fDaKn2nzmcdZxWUla5jmtR/NFI3uVN7RUU8+ePVyedXXZWkSnjp+JquHr0WRw0nK+aSRU5pdJ3etO40P469mbsNmorMayv2Suemudd76erWz85zGXflpYZ5IGRzsZyvkZ3yL6FUk0spxBblRleazYdyLGiL5yIi/13nLPgyslt9v5V2mca+VrYrdoyBtFGqlVYOreXp9fcZc0PElh9erTw3k3YJVbzPRXo9XOX1p8vzmePRw/JEoCRao2afZ+Uwuj7RqPZzJ75PEjnWXfeIABALPG42KxTs3LUyxQQppFam1Vy9yFapdWf8ApuFK0fc6zMsip4onT7EKVO8xhbd1vOSajw9NTfhx3D7WPigSexMiKxJeqMTxIHEMcSzUrHIkTrELXyI1O5V9OjOPLMrO3atZcXTL3Uh9Narl01FVfBDS3uHKsWOkswyzI6NnOnaImn+w9xVR+Px8VuGF0tu0vKxyN5kib4qT1sbNxfRy3qswqKneh4aPimlYSftmwIypC1sTF2nX5O8zinTDOZ47jGePTdAANMAAAAAAAAAAAHWvBJYnZDC3me9dIhyLPC5VuKlkk8mZM9yIjXKulb7CZbk7NYyW91hn8JFjcTWexm5tokr9qqKujOGv4qynZxrRWBrkmia/nVerV3/wZA5cHVcN5OnNMZlrELzhTCe7OSRJWu8liTmkcncv/jv1lGWOKy2QoPSGlZfG2R6ba3rte43yTK42Y+XF+pZvGxXcFPSTliYkfmehG8vVPk6H44pvuP8ANWatiKhVkfEjo1dI5q++RemvqUwKnm/o8MscN2+WsvIAD2MgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAXVHijKU4mw9s2eFqaSOZiOTXt7ylCGcsccvMGk/C5/f7lY7fj2Rxs8XZWaPs4ZI6sfdywMRv1958UuFcnbhSZY2V4l7nzu5EU45Xh+7i4UmlSOWBV12sTuZu/BTjjjwdWpra91Y975Hq+RyucvVXOXaqfIB6EaPH8QQ2ajcdnY1sVUTUcqJ58Ps8TnkeGJoa7ruOlZdooiu7Ri9WonihAw+JsZe2kMPmsb1kkX3rG+KlnmMxDVqe4+GXlqt6TTfpTr6fkPPZ0564/8An6KzpfY/hmW3XindZhYyTS6Rdrr7yg2SaMj0uQcrlTUjda9p2zmVnw3TWFx38U2mcQ2kmv8AYxtVsNZOyY1U13d5VIWnEuvd21r4SfuQqycfyw5PmqZkchLkZ2yzI1FaxGIjU6aQ8yF+XITtlmRqK1iMRGppERDtj8PZvwSzx8rIo0VVc9dIq+CFfra6Qs6fE9i9Xm+77fYmkajXyvcidERzlUsMNkLcVyvAyw9sLpWorN9NKpWqxyd7VT5D7rK9tmJ0Sc0iPRWp4rvoLJZpJbKncQyyuzNpjpHK1si6aq9EKw1GXoY+xecti+le69EdI1U2xF13bKm/hbFKHt1dHLBvSSRu2hz4+THUjpyYZbtVoAOziAAAAAAAAAAAeoEaq9yKoAmZTIvyUsckjGtcyNGeb6dEIAkkk1Fttu6EjH23Ub0NpjUc6J6ORru5TRScFvSvCrMjB5TLGj0gk8xV9hl3tVj3Md3tXSmcc8c/CLHPZmTN3ktSRMiVrEYjWrvptV+0rADUkxmoAAKAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAanhvHNr00y0tZbM738lOv8ADene75NL8xlj9MqMbBbrq1WpHj8YkjWrvq5ydXfV9Z5/6jPpx0sYq07K5nLsr23SdvLJyNY/aNb18PBC24fidWzN3h6zK2WCdro15e7nRNoqeC95eUM1TzT2ZF8jop8fC974Faip3dXIp2o8MUq+VistdZW1DqWSVfePcvecM+aSXHKa/wBrp+ZyxuilfG9NPYqtVPBUJmHxkmWvNrxvbGmlc97l6NanepxyMrZsjZlYu2Plc5vsVVI6LruPdd2dmWhzGXr16i4jDJyVE/KzfpTL9xnQCY4zGagFhgYfKM1VYvdz83zdfsK8uuGPxdi3YX+5ruci+Ck5LrGt8c3lEDKzeUZOzKv6UjtezfQjwo10zEe7lYrkRy+CHyp4hqTU0zbu7a7L4y5cWKCisLaEbU7PUmkX1qVNdK+FzjVnf5Q2JN80XjoqdrrvPDnjx2Tpt7OmXJLdyd2qt8S0LkLoJ61h8TlRVTaJsz1dnbZFjaq9mr5U7PmX3vXpsjHrUcrkRqKrvRo1jxzCaxTLkud7tdeSZMVZ92/Ju05fxCt1zq4yKuXXLtdeB2sxWY3otpkrXKn94i7X5zgpOPDphyZ9VeAHujo5vAe6U0/CvC65JEuXEVKqb5GIunSqn2GM88cMerIU2Nw97KP5akDnone9ejU9qlovDNSt5t/OVIJfSxic+hmMplLNpcVXrPpxMXkbVhTSr7dd/wC4g5Dh7IY2tDNaYxvau5Uja7b0X1oc95ZebrapNvhiRlR9rH3IL8EabesS+c35ChLbCW58Nm4JJEfE1XI2Rr01ti9+z74pxD8Vl5W8iNglcrodKnd/SmscrMunK7FMADqjZx204Y4dx09WKOSe67tJXPb1VvwSq4rpV6fEL2xIrYZUbJpqe9336I2SzHl+Mx9RYeV1Rit5975vDp8hxyOXsZC+y5JyslY1qN5E6Jy9x58OPKZdV/Xf+FW1ylwyyKRY7d6OXlXka+Loq66egz9Wbye1DNyI/s3o/ld3O0u9KWt/ijI5Gm+raWJ7H687s05k14KU8b1ilZI3Sq1UVN93Q6YTKT4ka3LRVeJa1jLUZJI7deNHT15F3pqJ3tMgae/xXFNVsMpY9lae4zlsS73tNa0hmDPDMscdVaAA7IAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGor5bHZPHRVcpYnp2IY+ybYi2qPZ4ORO8y4MZ4TIaZmJw0TXObxKjWObpyNiciqngWLuKaONgRtWzbyU6MVrHTeaxvyekxAOd4Jl812u3p4Ad0AAALzhxWSRX6iyNjlsRcsauXSenp9ZRnqGcp1TTWN6bt1tweTWZIVe16sXXMxdop7RdXbbjdba50CL57W96nFTwuu2k332vM7TZJbqvx9ZWtswo9sbE9P9aK/H03z5BsDoJJOV3nxs6O0nf3lonEKQ4mGGCPluMZ2far+i31FIyeWORZGSva9e9yO0pzw6+nVdM7jvcX2Vo1KtF7vcqxAvcyV0iL19fUpaFuWlbZNXRqyJ0RFbvvOb7E0jeWSV7k8HOVT4a5WPRzV05F2ip6DWONmOqmWct3Gpnbft8NS+XQyyWO2TskVnnInp6eHeZlnLFYalhjla1yc7O5db6oTPdzJr/62X5yBI90kjnvcrnOXaqvpUzx45Y7lXkymWrFy7K4qN3/AE+HYv6x6r9XU8/COVn9np1IvZFspQX0sfdPVyWU1qbN5CtHKkbHuc2JFa3Xevf9ZY8W33sy6U6rnQwUWpFGjV1pddV/rwM9G90cjZGOVrmrtFT0KaiebEcSI2ezZTHZHlRJFcm45Nen1GcpMbLrszbb3qywWemylK61Yo0ykNVVjsIicz0T7SFwXK2xbvzWLMSXnMakEs67VFXe1Tff6D6wuHkxmSjuVMrjZ2N21ze31zIqdUI1rh2q63LK/MY2sxzlc2Ns3Nyp4Hns4/ik7Si7z9Ttc/hEm7KyjXJG/qnPJ6VVU8OhV8f01S8y+ltkrJfMSNF6s0n7jhFX4fx06TPzVmeZnVFrM5frI+QzWNWlLUxuMbGkvvppl5pDXHjlMsde36aRnwAexAFji8Jfyyu8jgVzW++e5dNT5SPfo2MdbfWtM5JWd6d5nqxt6d9xGABoAXOdxVfFQUWJJItuWLtJmrrTd932kW7hshRjbJYqyNjc1HI9E23S+tDMzxogAA0AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAD7jifJzcjHO5U2uk3pPE+AAAAAAAAAAAAAAAAAAAAHelWfcuQ1o/fSvRieranAteGLMVTiCnNO7lja/Su8NoqfaTK2S2C3zeThrZKDERK6PGVHNbMkffIv6SqQryzcV8RyrTRreZPxaSLrzWoS73COVsZad7Gxuhlkc9J1kTl0q734lHKyPG5dW7iuRwSdfgya9BwwmGvgvfSpuR4XyGMpPtWlhaxqonKkm1XfgQsJW8szNOBU2j5W83s31+os72exlmpNFHgIIZJG6SVsnVq+KdCuwVxmPzNS1Kn4uOROb1J3Kal5Oi9XkWOVT3Z41fAqqjH2Eh9iJ0X9ymjq5Szd4tsUmK33MgjWORjk23lamt+3ZjbtxsHEE12hJzNSdZY3Kmt9d9xYZHip1qpNDWow1H2f7RIxdrJ9Rzy4rlJNe2v7G1BNyds/skVI+ZeXffr0HwAepAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEPVaqdSTQdUbK7y1sjo1YqJ2a6VF10U4OcmuVm9ev0gfAB0rsZJYjZJIkbHORHPVN8qb7wOYNHY4QtOb2uMsQX4fQsb0R3zFHapWab+SzXkhd4PaqGMeTHLxRwCAIbGgtSe4+FgrwoiWLsfPLJrryr+iULGOke1jGq5zl0iJ3qpc55e0x+Kn3vmg5V+RSmY5zHo5iq1zV2ip0VFOfF426cnnTQYzhG5bWXyt7aXI5I07RNq56ptEQqFx1pcg6gyFz7LXqzkam1VU7zW8X5N8lXBSscrO0RLDvbpul/eQ85erUON1uo1ZY2tRzkik0qqrNd6HHj5M73vvv8MVSXcHksfB21uo+KPeuZdd504dxXurk2xP82vGnaTO8Gp3lhleJ692jLUix6o1/c+ad0jmr4psrsJm5sLJM6GKKVszOR7ZE2iodJeS8d3O4u7a4+5gM1Zp0IYWxzRpE5GddbRN+rfX5zIG1r8Rz3+G8vzpWhdG1iMaxiIio7aL09JilHFvvL/OxQAHZAA9RNrpE2B4doatif8jBJJ/hYqmhr4yhg6cdzNsWazInNFTRddPFxHscX5V68tWSOpCnRI4Y0RE+VUOXXll8kVSzV5oF1NE+NfB7VQ5Gswueky1hMXm1bZgseY17mojo3ehUVDN36r6N6erJ76J6tX1mscrb05TuiOADY6+U2Oy7Lt5ez7uTnXXzHIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADpDPLA/nhkfG7xY5UU2E2Rs1uDlXLSJZnu7bXZIiKrG6994/0hncBRiv5WKKxKyOBu5JXOXXmp1VD64iynurlJJmpqFnmQt8Gp3HHPGZ5yfTuKwtcXgJ8lD2zZY449qm3L1+YqT6Rzu5FX5DrlLZ2rWNkvdoM/W8iwuOrOej3sc/zm9ypv/kzpd59fJqmPx+/Oij53/4ndSkMcXytcvzPt80sjWNkkc5GJpqOXfKngh8FuuBljx7rVixFC/k52wu985CvrUrNtypXhfIqd/Km9GpnjfDNwynmOB6SbeNt0mNfZgfE1y6RXE/EQQsxt+7YibI1jOzjR3wl/pBc5JsmNt0pzw1mMx2OlxFeK1Gkdm2rkjfvbl8F9SGZdEkVtYZl0jH8r1T0depMeSZWz6NZYXGSuINTNgcFO9JamehihVE8yVNuTx9KHx5FwrW/LZKzacnXUUekX+vaZ9bH2l/aubMl/wAJ1IX258hbTdahH2rkX9J3oQ7OzWBg/F1sA2WNP05pfOX6lLLH5KDMYfLUKePhpv7DnY2Ndq/S+z+tmOTPK4/LpVHkK9rJY+bPzzsdzz9mse+rfBD64fpVrONzE1iLtHQV+aNd65V69fqLLh21HW4PyD5akdtkVhrnRv7lRURCxwsOIyGOySYvtK7rLGxyxP69ntdbTxTqpzz5MscbNeLP8DBRSOimZKxdPY5HNXwVC+44ja3PrM1NJYhZL86a+wts7w7j62LtLVrTRTVnsYyV7tpOq62iJ8pV8cKiZeCHe3Q1Y2O9vVftN48k5M5cf1/wM4AWOFyjcTZfP5JFYerdM7T9BfE9Ftk7IhTQSwK1Jonxq5Noj2qm08Tmb23WfxI3h+xMjXdpz9vy9ERqKm/69Zno6uFnzF5J7T6tONy9kjG8yuTeuhyx5dzvO/8A6ulGC7zWPxVapHPjbk8qufyrHLEremu/fT1FIdMcplNxFziuGchlaq2YEjZDzcqOkdy7X1FbdqTUbclaw3lljXTkNtlKeRkuUcJjuaOnDDG6V6e93vfMq/JszfFtqG3xDalgVHM2jeZP0lRERVOPHyZZZd/CqYAHoQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB6eAAC04fqJYyLZJfyMCdrIq+Cf8lWX2IRZuH8jBW/tKqjlRO9zPV9Zz5LrF045vJVZG0t29NYd/eO2nqT0fUMb2XujX7fXZdo3m33a2R1TR4hvXbTG++60WZxWTu5eaRkDnxuXzHIqcvL6CNjLzcVJZrW1nVu9csD9JzJ6yuS7abH2bbMyM+Cj10cNmJhenpy8OlznV1Y+Vjlr9e4kaV2Tt5d77WVXbJEW04Qm0nRbfVf9KFKfaSSdksXO7s1XfLvpvx0W4dpIkz721fsztFrKsr6srrVWNGMTacm/EoJpXTTPlf757lcvtU+NAY4THwmWdy8gANsBNxGSkxWRitxdVYvnN+EnpQhAlks1Rto20LMFxMPk61Zl9upa1pNci/8AipHpYG/QbMlbNY+JsreVypN3onyGRBx9Gzxl+F23E+Wq4xiTXMj7s32/kmp+TiXx9v1mNt2pblqSzO5XSyO5nKcQbw45h3iAAOg0dXiZKnCy4yFj22VVze16aRirtdenZV4jKPxNp9iOGKV6sVje0TaNVddfqIAMTjxm5ryLPK57IZdjI7kqOYxdta1qIiKVgBqSSagtJeIcpNRbTfckWBE5dJ0VU8FX0lWAJjMfEAAFAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADvTtzUrDZ4H8j2/WcALN+SXS1yGVr3aytShFFYc5FfK30+wq07zwExxmM1FuVyu60bKWKfhLbq/NNPFG16yu2mlX0Ihn42o57UcvK1VRFdruQu+H7NKGjfjvP02RG+ane5E30QhZDJutWopIomQsg0kTGp3Ii+nxOeO5lY65auMqzbh8WxFXmv2Gom1dHEvL8+iinbCtpzaqvdErtM5+8l2M5kbHMj7T0aqa5W9E0VyLpdlwxynzVM8sb4jT2pqmIux061CKeZGNa97+u19nylVxHWhqZiaKBERnReVP0VVO4lLxLKupEqV/Kta7dW7cUs0r5pXSyuVz3rtVX0qZ48cpd1eTKWaj4AB2cQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAH//Z\n",
"text/html": [
"\n",
" \n",
" "
],
"text/plain": [
""
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from IPython.display import YouTubeVideo\n",
"YouTubeVideo('xOlhR_2QCXY')"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Item(index=0, weight=0, value=0),\n",
" Item(index=1, weight=1, value=5),\n",
" Item(index=2, weight=2, value=3),\n",
" Item(index=3, weight=4, value=5),\n",
" Item(index=4, weight=2, value=3),\n",
" Item(index=5, weight=5, value=2)]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Suppose there are five items, using the example from the above video.\n",
"## Let's assume that the 0th item has weight 0 and value 0, to make our indexing more intuitive.\n",
"\n",
"from collections import namedtuple\n",
"Item = namedtuple(\"Item\", ['index', 'weight', 'value'])\n",
"\n",
"item_count = 5\n",
"capacity = 10\n",
"input_data = [[0,0],[1,5],[2,3],[4,5],[2,3],[5,2]]\n",
"\n",
"items = []\n",
"for i in range(0, item_count+1):\n",
" line = input_data[i]\n",
" items.append(Item(i, int(line[0]), int(line[1])))\n",
" \n",
"items"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Set up our matrix V, which will be 6 rows and 11 columns.\n",
"## The row indices will range from i=0..5 and the column indices from j=0..10 \n",
"## V[i,j] equals the maximum value from the first i items, with total weight at most j.\n",
"\n",
"V = [[0]*(capacity+1) for x in range(0,item_count+1)]\n",
"V"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Complete the first step of our algorithm\n",
"for w in range(items[1].weight, capacity+1): \n",
" V[1][w]=items[1].value\n",
"V"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
" [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5],\n",
" [0, 5, 5, 8, 8, 8, 8, 8, 8, 8, 8],\n",
" [0, 5, 5, 8, 8, 10, 10, 13, 13, 13, 13],\n",
" [0, 5, 5, 8, 8, 11, 11, 13, 13, 16, 16],\n",
" [0, 5, 5, 8, 8, 11, 11, 13, 13, 16, 16]]"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Complete the remaining steps of our algorithm, one object at a time.\n",
"for i in range(1,len(items)):\n",
" x=items[i]\n",
" for w in range(0,capacity+1):\n",
" if x.weight>w: V[i][w]=V[i-1][w]\n",
" else: V[i][w]=max(V[i-1][w],x.value+V[i-1][w-x.weight])\n",
"V"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"16"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"optimal_value=V[item_count][capacity]\n",
"optimal_value"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Item(index=4, weight=2, value=3),\n",
" Item(index=3, weight=4, value=5),\n",
" Item(index=2, weight=2, value=3),\n",
" Item(index=1, weight=1, value=5)]"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Now we know that the optimal solution has value=16. Let's figure out which items were chosen.\n",
"## Can you figure out how this code works?\n",
"\n",
"chosen_items=[]\n",
"i=item_count\n",
"w=capacity\n",
"while i>=0 and w>=0:\n",
" if V[i][w]!=V[i-1][w]: \n",
" if items[i].weight>0: chosen_items.append(items[i])\n",
" w=w-items[i].weight\n",
" i=i-1\n",
"chosen_items"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[Item(index=0, weight=0, value=0),\n",
" Item(index=1, weight=1945, value=4990),\n",
" Item(index=2, weight=321, value=1142),\n",
" Item(index=3, weight=2945, value=7390),\n",
" Item(index=4, weight=4136, value=10372),\n",
" Item(index=5, weight=1107, value=3114),\n",
" Item(index=6, weight=1022, value=2744),\n",
" Item(index=7, weight=1101, value=3102),\n",
" Item(index=8, weight=2890, value=7280),\n",
" Item(index=9, weight=962, value=2624),\n",
" Item(index=10, weight=1060, value=3020),\n",
" Item(index=11, weight=805, value=2310),\n",
" Item(index=12, weight=689, value=2078),\n",
" Item(index=13, weight=1513, value=3926),\n",
" Item(index=14, weight=3878, value=9656),\n",
" Item(index=15, weight=13504, value=32708),\n",
" Item(index=16, weight=1865, value=4830),\n",
" Item(index=17, weight=667, value=2034),\n",
" Item(index=18, weight=1833, value=4766),\n",
" Item(index=19, weight=16553, value=40006)]"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"## Now let's try a super-hard example!\n",
"\n",
"item_count = 19\n",
"capacity = 31181\n",
"\n",
"input_data=[[0,0],[1945, 4990],[321, 1142],[2945, 7390],[4136, 10372],[1107, 3114],[1022, 2744],[1101, 3102],[2890, 7280],\n",
"[962, 2624],[1060, 3020],[805, 2310],[689, 2078],[1513, 3926],[3878, 9656],[13504, 32708],[1865, 4830],[667, 2034],[1833, 4766],\n",
"[16553, 40006]]\n",
"\n",
"items = []\n",
"for i in range(0, item_count+1):\n",
" line = input_data[i]\n",
" items.append(Item(i, int(line[0]), int(line[1])))\n",
" \n",
"items"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Optimal Value is 79954 and our Total Capacity is 31181\n",
"And below are our chosen items with total weight 31177 and total value 79954\n"
]
},
{
"data": {
"text/plain": [
"[Item(index=18, weight=1833, value=4766),\n",
" Item(index=17, weight=667, value=2034),\n",
" Item(index=16, weight=1865, value=4830),\n",
" Item(index=15, weight=13504, value=32708),\n",
" Item(index=13, weight=1513, value=3926),\n",
" Item(index=12, weight=689, value=2078),\n",
" Item(index=11, weight=805, value=2310),\n",
" Item(index=10, weight=1060, value=3020),\n",
" Item(index=9, weight=962, value=2624),\n",
" Item(index=8, weight=2890, value=7280),\n",
" Item(index=7, weight=1101, value=3102),\n",
" Item(index=6, weight=1022, value=2744),\n",
" Item(index=3, weight=2945, value=7390),\n",
" Item(index=2, weight=321, value=1142)]"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"totalw=0\n",
"totalv=0\n",
"V = [[0]*(capacity+1) for x in range(0,item_count+1)]\n",
"for w in range(items[1].weight, capacity+1): \n",
" V[1][w]=items[1].value\n",
"for i in range(1,len(items)):\n",
" x=items[i]\n",
" for w in range(0,capacity+1):\n",
" if x.weight>w: V[i][w]=V[i-1][w]\n",
" else: V[i][w]=max(V[i-1][w],x.value+V[i-1][w-x.weight])\n",
"optimal_value=V[item_count][capacity]\n",
"chosen_items=[]\n",
"i=item_count\n",
"w=capacity\n",
"while i>=0 and w>=0:\n",
" if V[i][w]!=V[i-1][w]: \n",
" if items[i].weight>0: \n",
" chosen_items.append(items[i])\n",
" totalw=items[i].weight+totalw\n",
" totalv=items[i].value+totalv\n",
" w=w-items[i].weight\n",
" i=i-1\n",
"print(\"Optimal Value is\", optimal_value, \"and our Total Capacity is\", capacity)\n",
"print(\"And below are our chosen items with total weight\", totalw, \"and total value\", totalv)\n",
"chosen_items"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"![alt text](https://github.com/callysto/callysto-sample-notebooks/blob/master/notebooks/images/Callysto_Notebook-Banners_Bottom_06.06.18.jpg?raw=true)"
]
}
],
"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.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}