{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "4d65ee86-e6ea-46f3-a23b-f7842fd0248b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Item ID\tWeight\tWorth\n",
      "1\t8\t491\n",
      "2\t3\t512\n",
      "3\t9\t246\n",
      "4\t2\t75\n",
      "5\t5\t306\n",
      "6\t11\t444\n",
      "7\t9\t426\n",
      "8\t12\t74\n",
      "9\t8\t143\n",
      "10\t12\t159\n",
      "Initial population: \n",
      "[[0 0 0 1 0 1 0 0 0 1]\n",
      " [0 1 1 1 1 0 0 1 0 0]\n",
      " [1 1 1 0 1 0 1 1 0 1]\n",
      " [1 0 1 1 1 0 0 1 0 0]\n",
      " [1 1 1 0 1 1 1 1 0 1]\n",
      " [1 0 0 0 0 1 0 0 0 0]\n",
      " [1 1 0 1 0 0 0 1 0 0]\n",
      " [1 1 0 1 1 0 0 1 1 1]\n",
      " [0 0 0 1 0 1 0 1 0 0]\n",
      " [0 0 0 0 0 1 1 0 0 0]]\n",
      "\n",
      "Selected items that will maximize the knapsack without breaking it:\n",
      "1\n",
      "2\n",
      "4\n",
      "7\n",
      "10\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAkQAAAHHCAYAAABeLEexAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy81sbWrAAAACXBIWXMAAA9hAAAPYQGoP6dpAABI/0lEQVR4nO3deXQUVd7G8aezdUIgCRAghC1ssimIQTAgCBLZHBY3RBkHFWGUIIiIgr4iOCqICrKDowPKMKPjxowoSlwgyoCymAERImBYFGKUJSEBkpDc9w/swiaJZOlOdyffzzl9Dl1103Wr0lAPVb9b12aMMQIAAKjC/DzdAQAAAE8jEAEAgCqPQAQAAKo8AhEAAKjyCEQAAKDKIxABAIAqj0AEAACqPAIRAACo8ghEAACgyiMQAW4WExOjO++809PdqFAxMTH6wx/+4OlulFnPnj116aWXuvxzp02bJpvNpl9++cXlnw1ny5cvl81m0/79+z3dFfgIAhF8ks1mK9Fr3bp1bu3H/v37i932VVddVeTPfPvtt5o2bZrP/0NdWfbDHZ555hmtWrXK092oEjjWcJUAT3cAKIsVK1Y4vX/ttdeUmJhYaHmbNm0qpD+33XabBgwY4LSsTp06kqSUlBT5+Z3/v8e3336r6dOnq2fPnoqJiamQ/rlDZdkPd3jmmWd08803a8iQIZ7uSqVX3LG+4447NGzYMNntds90DD6HQASf9Mc//tHp/aZNm5SYmFhoeUW54oorit02/yCXTnZ2tkJDQz3dDXhAQUGBcnNzFRwcXO7P8vf3l7+/vwt6haqCW2aotLKzszVx4kQ1atRIdrtdrVq10vPPPy9jjFM7m82msWPHauXKlWrVqpWCg4MVGxurpKQkl/TjtzVEy5cv1y233CJJ6tWrV6Fbe47amy+++EKdO3dWcHCwmjVrptdee63Q5544cUIPPPCAtX8tWrTQs88+q4KCAqd2r7/+umJjY1WjRg2FhYXpsssu09y5c631eXl5mj59ulq2bKng4GDVrl1bV199tRITE4vdp4vth8PF9sNR57F+/XqNGTNGdevWVcOGDa31ixYtUrt27WS32xUdHa2EhASdOHGi2OP7Wz179lTPnj2dlh04cECDBg1SaGio6tatqwkTJuijjz4q9vbqt99+q169eqlatWpq0KCBZs2aVewxcbDZbMrOztarr75qHZcL+3fixAndeeedioiIUHh4uO666y6dOnWq0Gf9/e9/V2xsrEJCQlSrVi0NGzZMhw4dumgfJGndunXq1KmTgoOD1bx5cy1dutSqYSrLdhx1VSU5Jjk5OXriiSfUokUL2e12NWrUSA8//LBycnIKHSvH3z3H7/nDDz+UJD3//PPq2rWrateurZCQEMXGxuqtt94q8bEuroaoJN+p0uzr/Pnz1a5dO1WrVk01a9ZUp06d9I9//KPI3wm8nAEqgYSEBPPbr3NBQYG59tprjc1mM/fcc49ZsGCBGThwoJFkHnjgAaeflWQuvfRSExkZaZ588knz7LPPmiZNmpiQkBCzY8eO391uamqqkWSmT59ufv75Z6dXbm6uMcaYJk2amBEjRhhjjNm3b58ZN26ckWQeffRRs2LFCrNixQqTlpZmtW3VqpWpV6+eefTRR82CBQvMFVdcYWw2m/nmm2+s7WZnZ5v27dub2rVrm0cffdQsWbLE/OlPfzI2m82MHz/eard27VojyfTu3dssXLjQLFy40IwdO9bccsstVptHH33U2Gw2M2rUKPPXv/7VvPDCC+a2224zM2fOLHa/XbUfy5YtM5JM27ZtzTXXXGPmz59vbfeJJ54wkkx8fLyZP3++GTt2rPH39zdXXnmldWwvPL6/dc0115hrrrnGep+VlWWaNWtmQkJCzOTJk82LL75oOnfubDp06GAkmc8++8zpZ6Ojo02jRo3M+PHjzaJFi8y1115rJJkPPvig2ONijDErVqwwdrvddO/e3Tou//3vf532qWPHjubGG280ixYtMvfcc4+RZB5++GGnz3nqqaeMzWYzt956q1m0aJGZPn26iYyMNDExMeb48eO/24dt27YZu91uYmJizMyZM83TTz9toqOjrX0ty3ZKekzy8/NNnz59TLVq1cwDDzxgli5dasaOHWsCAgLM4MGDnbYtybRp08bUqVPHTJ8+3SxcuNB8/fXXxhhjGjZsaMaMGWMWLFhgZs+ebTp37mwkmdWrV5foWDu+W6mpqVb7kn6nSrqvL730kpFkbr75ZrN06VIzd+5cM3LkSDNu3Ljf/f3AOxGIUClcGIhWrVplJJmnnnrKqd3NN99sbDab2bt3r7VMkpFktmzZYi07cOCACQ4ONjfccMPvbtcRiIp6OU6wF56w33zzzUInYIcmTZoYSSYpKclalp6ebux2u5k4caK17C9/+YsJDQ013333ndPPT5482fj7+5uDBw8aY4wZP368CQsLM2fPni12Hzp06GCuv/76393PorhiPxwnrauvvtqpj+np6SYoKMj06dPH5OfnW8sXLFhgJJm//e1vTtsqSSB64YUXjCSzatUqa9np06dN69atiwxEksxrr71mLcvJyTFRUVHmpptuuuixCQ0NLbJPjhPy3Xff7bT8hhtuMLVr17be79+/3/j7+5unn37aqd2OHTtMQEBAoeUXGjhwoKlWrZr58ccfrWV79uwxAQEBTn9PSrOdkh6TFStWGD8/P/P55587feaSJUuMJLNhwwZrmSTj5+dndu7cWWgfTp065fQ+NzfXXHrppebaa691Wl7csb4wEJXmO1XSfR08eLBp165doW3DN3HLDJXSBx98IH9/f40bN85p+cSJE2WM0Zo1a5yWx8XFKTY21nrfuHFjDR48WB999JHy8/Mvur3Ro0crMTHR6dWhQ4cy9b1t27bq3r279b5OnTpq1aqVvv/+e2vZm2++qe7du6tmzZr65ZdfrFd8fLzy8/Ot230RERHKzs7+3dtfERER2rlzp/bs2VOm/pZnPxxGjRrlVO/x8ccfKzc3Vw888IBTQfqoUaMUFham999/v9T9+fDDD9WgQQMNGjTIWhYcHKxRo0YV2b569epOdWFBQUHq3Llzkf0vrXvvvdfpfffu3XX06FFlZmZKkt555x0VFBRo6NChTr/fqKgotWzZUp999lmxn52fn6+PP/5YQ4YMUXR0tLW8RYsW6t+/v1Pb0m6nJMfkzTffVJs2bdS6dWunz7z22mslqdBnXnPNNWrbtm2h/QgJCbH+fPz4cWVkZKh79+7atm1bsfv+e0r7nSrJvkZEROiHH37Q5s2by9QneBeKqlEpHThwQNHR0apRo4bTcseoswMHDjgtb9myZaHPuOSSS3Tq1Cn9/PPPioqK+t3ttWzZUvHx8eXs9TmNGzcutKxmzZo6fvy49X7Pnj3avn27NZLtQunp6ZKkMWPG6F//+pf69++vBg0aqE+fPho6dKj69etntX3yySc1ePBgXXLJJbr00kvVr18/3XHHHWrfvr3b98OhadOmTu8dv59WrVo5LQ8KClKzZs0K/f5K4sCBA2revHmhGpoWLVoU2b5hw4aF2tasWVPbt28v9bYvdOGxqVmzpqRzJ/6wsDDt2bNHxpgiv5eSFBgYWOxnp6en6/Tp00Xu14XLSrudkhyTPXv2aNeuXRf9bjpc+Lt3WL16tZ566iklJyc71R4VVQNVEqX9TpVkXx955BF9/PHH6ty5s1q0aKE+ffro9ttvV7du3crUR3gWgQjwMsWNjDG/KQYvKCjQddddp4cffrjItpdccokkqW7dukpOTtZHH32kNWvWaM2aNVq2bJn+9Kc/6dVXX5Uk9ejRQ/v27dO///1vrV27Vi+//LLmzJmjJUuW6J577nHrfjj89mpAaRV3gszPzy/XKKPS9N/Vn11QUCCbzaY1a9YU2bZ69erl7kNZtlPS7+Zll12m2bNnF9m2UaNGTu+L+t1//vnnGjRokHr06KFFixapfv36CgwM1LJlyyqsYLkk+9qmTRulpKRo9erV+vDDD/X2229r0aJFmjp1qqZPn14h/YTrEIhQKTVp0kQff/yxTp486XSVaPfu3db63yrqdtF3332natWqFfs/3bIq6/9wf6t58+bKysoq0VWpoKAgDRw4UAMHDlRBQYHGjBmjpUuX6vHHH7euGNSqVUt33XWX7rrrLmVlZalHjx6aNm3a7wYiV+xHcRy/n5SUFDVr1sxanpubq9TUVKf9rlmzZqFRQtK5KwK//dkmTZro22+/lTHGqe979+51ef/Le2yaN28uY4yaNm1qhduSqlu3roKDg4vcrwuXlWc7xWnevLn+97//qXfv3mU+Dm+//baCg4P10UcfOT22YtmyZYXalnQbpflOlUZoaKhuvfVW3XrrrcrNzdWNN96op59+WlOmTHHJ4wNQcaghQqU0YMAA5efna8GCBU7L58yZI5vNVqiWYuPGjU61CYcOHdK///1v9enTx+XPMnE8Y6eok3hJDR06VBs3btRHH31UaN2JEyd09uxZSdLRo0ed1vn5+Vm3why3IS5sU716dbVo0aLQEOkLuWI/ihMfH6+goCDNmzfP6X/kr7zyijIyMnT99ddby5o3b65NmzYpNzfXWrZ69epCw8b79u2rH3/8Uf/5z3+sZWfOnNFf//pXl/c/NDS0XMflxhtvlL+/v6ZPn17oipQxptDv7Lf8/f0VHx+vVatW6fDhw9byvXv3FqqdK892ijN06FD9+OOPRR7X06dPKzs7+6Kf4e/vL5vN5lS/t3///iKfSF3SY12a71RJXXh8goKC1LZtWxljlJeXV+rPg2dxhQiV0sCBA9WrVy899thj2r9/vzp06KC1a9fq3//+tx544AE1b97cqf2ll16qvn37aty4cbLb7Vq0aJEkueWy9+WXXy5/f389++yzysjIkN1u17XXXqu6deuW+DMmTZqk//znP/rDH/6gO++8U7GxscrOztaOHTv01ltvaf/+/YqMjNQ999yjY8eO6dprr1XDhg114MABzZ8/X5dffrlVT9W2bVv17NlTsbGxqlWrlrZs2aK33npLY8eOdft+FKdOnTqaMmWKpk+frn79+mnQoEFKSUnRokWLdOWVVzoVu95zzz1666231K9fPw0dOlT79u3T3//+90K/4z//+c9asGCBbrvtNo0fP17169fXypUrrf/Fu/KKV2xsrD7++GPNnj1b0dHRatq0qbp06VLin2/evLmeeuopTZkyRfv379eQIUNUo0YNpaam6t1339Xo0aP10EMPFfvz06ZN09q1a9WtWzfdd9991n8OLr30UiUnJ7tsO0W544479K9//Uv33nuvPvvsM3Xr1k35+fnavXu3/vWvf+mjjz5Sp06dfvczrr/+es2ePVv9+vXT7bffrvT0dC1cuFAtWrQoVMNV0mNdmu9USfXp00dRUVHq1q2b6tWrp127dmnBggW6/vrrC9UvwgdU8Kg2wC0uHHZvjDEnT540EyZMMNHR0SYwMNC0bNnSPPfcc6agoMCpnSSTkJBg/v73v5uWLVsau91uOnbsWORw8gs5ht0/99xzxbYpalj4X//6V9OsWTPj7+9faIh+UUPgLxxC7ti/KVOmmBYtWpigoCATGRlpunbtap5//nnrmSpvvfWW6dOnj6lbt64JCgoyjRs3Nn/+85/NkSNHrM956qmnTOfOnU1ERIQJCQkxrVu3Nk8//bTTc1mKU979cAyN3rx5c5Gfv2DBAtO6dWsTGBho6tWrZ+67774in8HzwgsvmAYNGhi73W66detmtmzZUuQx+/777831119vQkJCTJ06dczEiRPN22+/bSSZTZs2OfWzqOHUI0aMME2aNLnocdm9e7fp0aOHCQkJMZKs379j2P3PP//s1L6oZ+YYY8zbb79trr76ahMaGmpCQ0NN69atTUJCgklJSbloHz755BPTsWNHExQUZJo3b25efvllM3HiRBMcHFyobUm2U5pjkpuba5599lnTrl07Y7fbTc2aNU1sbKyZPn26ycjIsNo5/u4V5ZVXXrH+PrZu3dosW7bMOn6/VdyxLu6YluQ7VdJ9Xbp0qenRo4epXbu2sdvtpnnz5mbSpElO+wjfYTPGBRWCgA+z2WxKSEgodHsNVcOLL76oCRMm6IcfflCDBg083R23GjJkiFsesQBUBtQQAagyTp8+7fT+zJkzWrp0qVq2bFnpwtCF+7pnzx598MEHhaYzAXAONUQAqowbb7xRjRs31uWXX66MjAz9/e9/1+7du7Vy5UpPd83lmjVrpjvvvNN6xs7ixYsVFBRU7KMagKqOQASgyujbt69efvllrVy5Uvn5+Wrbtq1ef/113XrrrZ7umsv169dP//znP5WWlia73a64uDg988wzxT6EEajqqCECAABVHjVEAACgyiMQAQCAKo8aohIqKCjQ4cOHVaNGDbdOWQAAAFzHGKOTJ08qOjpafn7FXwciEJXQ4cOHC01KCAAAfMOhQ4fUsGHDYtcTiErI8Rj2Q4cOKSwszMO9AQAAJZGZmalGjRpddDoVAlEJOW6ThYWFEYgAAPAxFyt3oagaAABUeQQiAABQ5RGIAABAlUcgAgAAVR6BCAAAVHkEIgAAUOURiAAAQJVHIAIAAFUegQgAAFR5BCIAAFDlEYgAAECVRyACAABVHpO7wm2MMUrLPKP8AuPprgAAfECDiJCLTsLqLgQiuM30977V8v/u93Q3AAA+4run+isogECESmZdSrokKcjfTx4K/AAAlAiBCG6Rl1+gQ8dPS5LWP9xT9cNDPNwjAACKR1E13OKH46eVX2AUHOinejWCPd0dAAB+F4EIbrH/l2xJUkztUPn5cb8MAODdCERwi9TfBCIAALwdgQhusf/or4EokkAEAPB+BCK4heMKUdPIah7uCQAAF0cgglucD0TVPdwTAAAujkAEl8s5m6/DJ84NuY/hChEAwAcQiOByh46dUoGRQoP8Vae63dPdAQDgoghEcLnUX05JOldQ7ak5aQAAKA0CEVzOegYRI8wAAD6CQASXS/11yH1TnkEEAPARBCK4HFeIAAC+hkAEl9vPM4gAAD6GQASXOp2br8MZZyQxbQcAwHcQiOBSB46duzoUFhygWqFBHu4NAAAlQyCCS52/XcaQewCA7yAQwaV++wwiAAB8BYEILmWNMKN+CADgQwhEcCnrGURcIQIA+BACEVyKZxABAHwRgQguk51zVukncyTxlGoAgG8hEMFl9v96u6xmtUCFVwv0cG8AACg5AhFcZj8jzAAAPopABJdJ/SVLEgXVAADfQyCCyzieQUT9EADA1xCI4DKOGiJumQEAfA2BCC7z22k7AADwJQQiuETmmTwdzc6VxBUiAIDvIRDBJRxXhyKr21XdHuDh3gAAUDoEIrhEqnW7rJqHewIAQOkRiOAS1jOIGGEGAPBBBCK4BCPMAAC+jEAEl/ieEWYAAB9GIIJLMOQeAODLCEQot+PZuco4nSeJGiIAgG8iEKHcUn+tH4oKC1ZIkL+HewMAQOkRiFBujttlMQy5BwD4KAIRyo36IQCAryMQodxSj/IMIgCAbyMQodzO3zIjEAEAfBOBCOVijOGWGQDA53k0ECUlJWngwIGKjo6WzWbTqlWrCrXZtWuXBg0apPDwcIWGhurKK6/UwYMHrfVnzpxRQkKCateurerVq+umm27STz/95PQZBw8e1PXXX69q1aqpbt26mjRpks6ePevu3asSfsnK1cmcs7LZpMa1KKoGAPgmjwai7OxsdejQQQsXLixy/b59+3T11VerdevWWrdunbZv367HH39cwcHBVpsJEybovffe05tvvqn169fr8OHDuvHGG631+fn5uv7665Wbm6v//ve/evXVV7V8+XJNnTrV7ftXFTim7IgOD1FwIEPuAQC+yWaMMZ7uhCTZbDa9++67GjJkiLVs2LBhCgwM1IoVK4r8mYyMDNWpU0f/+Mc/dPPNN0uSdu/erTZt2mjjxo266qqrtGbNGv3hD3/Q4cOHVa9ePUnSkiVL9Mgjj+jnn39WUFBQifqXmZmp8PBwZWRkKCwsrHw7W4n8a8shPfzWdl3dIlJ/v6eLp7sDAICTkp6/vbaGqKCgQO+//74uueQS9e3bV3Xr1lWXLl2cbqtt3bpVeXl5io+Pt5a1bt1ajRs31saNGyVJGzdu1GWXXWaFIUnq27evMjMztXPnzmK3n5OTo8zMTKcXCuMZRACAysBrA1F6erqysrI0c+ZM9evXT2vXrtUNN9ygG2+8UevXr5ckpaWlKSgoSBEREU4/W69ePaWlpVltfhuGHOsd64ozY8YMhYeHW69GjRq5cO8qD2uWe4bcAwB8mNcGooKCAknS4MGDNWHCBF1++eWaPHmy/vCHP2jJkiVu3/6UKVOUkZFhvQ4dOuT2bfqi1F/OPYOIEWYAAF/mtYEoMjJSAQEBatu2rdPyNm3aWKPMoqKilJubqxMnTji1+emnnxQVFWW1uXDUmeO9o01R7Ha7wsLCnF5wZozRgaM8gwgA4Pu8NhAFBQXpyiuvVEpKitPy7777Tk2aNJEkxcbGKjAwUJ988om1PiUlRQcPHlRcXJwkKS4uTjt27FB6errVJjExUWFhYYXCFkon/WSOTuXmy88mNapJDREAwHcFeHLjWVlZ2rt3r/U+NTVVycnJqlWrlho3bqxJkybp1ltvVY8ePdSrVy99+OGHeu+997Ru3TpJUnh4uEaOHKkHH3xQtWrVUlhYmO6//37FxcXpqquukiT16dNHbdu21R133KFZs2YpLS1N//d//6eEhATZ7XZP7HalkfprQXXDmtUUFOC12RoAgIvyaCDasmWLevXqZb1/8MEHJUkjRozQ8uXLdcMNN2jJkiWaMWOGxo0bp1atWuntt9/W1Vdfbf3MnDlz5Ofnp5tuukk5OTnq27evFi1aZK339/fX6tWrdd999ykuLk6hoaEaMWKEnnzyyYrb0UoqlSk7AACVhNc8h8jb8RyiwmZ8sEtLk77XnV1jNG1QO093BwCAQnz+OUTwftYVotrUDwEAfBuBCGW2nxFmAIBKgkCEMikoMDpwlGcQAQAqBwIRyuRI5hnlnC1QgJ9NDSJCPN0dAADKhUCEMnHMYda4VjUF+PM1AgD4Ns5kKBOG3AMAKhMCEcrEmuWeSV0BAJUAgQhl4hhh1jSSIfcAAN/n0SdVw3UOHj2lhZ/t1am8/ArZ3ub9xyVxywwAUDkQiCqJ1zbu1xtbDlXoNv39bGpVr0aFbhMAAHcgEFUSx7JzJUl92tZTXPPaFbLNVlE1VDcsuEK2BQCAOxGIKomTOWclST1b1dXtXRp7uDcAAPgWiqoriZNn8iRJ1YPJuAAAlBaBqJLI+vUKUQ0CEQAApUYgqiROnvk1ENkJRAAAlBaBqJKwAlFwoId7AgCA7yEQVRJZvwYiaogAACg9AlElcCYvX7n5BZKoIQIAoCwIRJWAo6BakqoHEYgAACgtAlEl4Kgfqm4PkJ+fzcO9AQDA9xCIKoGsMwy5BwCgPAhElYD1UEaG3AMAUCYEokrgJA9lBACgXAhElYBVQ8QziAAAKBMCUSWQ9estM64QAQBQNgSiSoBpOwAAKB8CUSXAxK4AAJQPgagSyLSeQ0QNEQAAZUEgqgROUkMEAEC5EIgqAcctMyZ2BQCgbAhElYCjqDqMQAQAQJkQiCqBLGqIAAAoFwJRJUANEQAA5UMgqgSYugMAgPIhEPm4ggJDUTUAAOVEIPJxp/LyZcy5P4cxlxkAAGVCIPJxjvqhAD+b7AH8OgEAKAvOoD7OMcKsRnCAbDabh3sDAIBvIhD5OGvaDuqHAAAoMwKRj7OG3PMMIgAAyoxA5OMYYQYAQPkRiHwc03YAAFB+BCIfd37aDgIRAABlRSDyceen7aCGCACAsiIQ+biT1BABAFBuBCIfd/IM85gBAFBeBCIfd/7BjNwyAwCgrAhEPu5kjuM5RFwhAgCgrAhEPi6LW2YAAJQbgcjHnWTYPQAA5UYg8nGOUWbUEAEAUHYEIh93/jlEXCECAKCsCEQ+LC+/QGfyCiQRiAAAKA8CkQ9zFFRLUig1RAAAlBmByIc5CqpDAv0V6M+vEgCAsuIs6sMczyBi2g4AAMqHQOTDmLYDAADXIBD5MOuhjNQPAQBQLgQiH2ZN28EziAAAKBcCkQ/L4inVAAC4BIHIh2VSQwQAgEsQiHxYFtN2AADgEgQiH+aYtoNh9wAAlI9HA1FSUpIGDhyo6Oho2Ww2rVq1ymn9nXfeKZvN5vTq16+fU5tjx45p+PDhCgsLU0REhEaOHKmsrCynNtu3b1f37t0VHBysRo0aadasWe7etQrhGHYfRiACAKBcPBqIsrOz1aFDBy1cuLDYNv369dORI0es1z//+U+n9cOHD9fOnTuVmJio1atXKykpSaNHj7bWZ2Zmqk+fPmrSpIm2bt2q5557TtOmTdNLL73ktv2qKBRVAwDgGh49k/bv31/9+/f/3TZ2u11RUVFFrtu1a5c+/PBDbd68WZ06dZIkzZ8/XwMGDNDzzz+v6OhorVy5Urm5ufrb3/6moKAgtWvXTsnJyZo9e7ZTcPJF5x/MSA0RAADl4fU1ROvWrVPdunXVqlUr3XfffTp69Ki1buPGjYqIiLDCkCTFx8fLz89PX375pdWmR48eCgoKstr07dtXKSkpOn78eMXtiBuc/LWomhoiAADKx6vPpP369dONN96opk2bat++fXr00UfVv39/bdy4Uf7+/kpLS1PdunWdfiYgIEC1atVSWlqaJCktLU1NmzZ1alOvXj1rXc2aNYvcdk5OjnJycqz3mZmZrtw1l3AUVTPsHgCA8vHqM+mwYcOsP1922WVq3769mjdvrnXr1ql3795u3faMGTM0ffp0t26jvKxh99QQAQBQLl5/y+y3mjVrpsjISO3du1eSFBUVpfT0dKc2Z8+e1bFjx6y6o6ioKP30009ObRzvi6tNkqQpU6YoIyPDeh06dMiVu1JuxhhqiAAAcBGfCkQ//PCDjh49qvr160uS4uLidOLECW3dutVq8+mnn6qgoEBdunSx2iQlJSkvL89qk5iYqFatWhV7u0w6V8wdFhbm9PImZ/IKlF9gJFFDBABAeXk0EGVlZSk5OVnJycmSpNTUVCUnJ+vgwYPKysrSpEmTtGnTJu3fv1+ffPKJBg8erBYtWqhv376SpDZt2qhfv34aNWqUvvrqK23YsEFjx47VsGHDFB0dLUm6/fbbFRQUpJEjR2rnzp164403NHfuXD344IOe2m2XcNQP2WxSaJC/h3sDAIBv82gg2rJlizp27KiOHTtKkh588EF17NhRU6dOlb+/v7Zv365Bgwbpkksu0ciRIxUbG6vPP/9cdrvd+oyVK1eqdevW6t27twYMGKCrr77a6RlD4eHhWrt2rVJTUxUbG6uJEydq6tSpvj/kPuf8M4hsNpuHewMAgG+zGWOMpzvhCzIzMxUeHq6MjAyvuH2WfOiEhizcoAYRIdow+VpPdwcAAK9U0vO3T9UQ4TyeUg0AgOsQiHwUzyACAMB1CEQ+6vyQewIRAADl5ZJAdOLECVd8DErh/LQdPIMIAIDyKnUgevbZZ/XGG29Y74cOHaratWurQYMG+t///ufSzqF43DIDAMB1Sh2IlixZokaNGkk694DDxMRErVmzRv3799ekSZNc3kEUzVFUzbQdAACUX6nPpmlpaVYgWr16tYYOHao+ffooJibGejo03I8aIgAAXKfUV4hq1qxpzev14YcfKj4+XtK5ubXy8/Nd2zsUKyuHYfcAALhKqc+mN954o26//Xa1bNlSR48eVf/+/SVJX3/9tVq0aOHyDqJomVYNEUXVAACUV6kD0Zw5cxQTE6NDhw5p1qxZql69uiTpyJEjGjNmjMs7iKJZV4i4ZQYAQLmV+mwaGBiohx56qNDyCRMmuKRDKBlqiAAAcJ1S1xC9+uqrev/99633Dz/8sCIiItS1a1cdOHDApZ1D8c6PMuOWGQAA5VXqQPTMM88oJCREkrRx40YtXLhQs2bNUmRkJFeJKhDPIQIAwHVKfTY9dOiQVTy9atUq3XTTTRo9erS6deumnj17urp/KEJ+gVF27rkRfdQQAQBQfqW+QlS9enUdPXpUkrR27Vpdd911kqTg4GCdPn3atb1DkRwF1RJXiAAAcIVSn02vu+463XPPPerYsaO+++47DRgwQJK0c+dOxcTEuLp/KILjdllQgJ/sAf4e7g0AAL6v1FeIFi5cqLi4OP388896++23Vbt2bUnS1q1bddttt7m8gyjMcYWIaTsAAHCNUp9RIyIitGDBgkLLp0+f7pIO4eIYcg8AgGuV+gqRJH3++ef64x//qK5du+rHH3+UJK1YsUJffPGFSzuHojmG3FNQDQCAa5Q6EL399tvq27evQkJCtG3bNuXk5EiSMjIy9Mwzz7i8gyjMmraDZxABAOASpQ5ETz31lJYsWaK//vWvCgw8f0Lu1q2btm3b5tLOoWhM2wEAgGuVOhClpKSoR48ehZaHh4frxIkTrugTLoIaIgAAXKvUgSgqKkp79+4ttPyLL75Qs2bNXNIp/L7z03YQiAAAcIVSB6JRo0Zp/Pjx+vLLL2Wz2XT48GGtXLlSDz30kO677z539BEXOD9tBzVEAAC4QqkvMUyePFkFBQXq3bu3Tp06pR49eshut+uhhx7S/fff744+4gInqSECAMClSn1GtdlseuyxxzRp0iTt3btXWVlZatu2rapXr+6O/qEI1BABAOBaZT6jBgUFqW3btq7sC0rIccusOjVEAAC4RKnPqNnZ2Zo5c6Y++eQTpaenq6CgwGn9999/77LOoWiOYfdh1BABAOASpQ5E99xzj9avX6877rhD9evXl81mc0e/8DtO8qRqAABcqtRn1DVr1uj9999Xt27d3NEflEAWNUQAALhUqYfd16xZU7Vq1XJHX1BC54uquWUGAIArlDoQ/eUvf9HUqVN16tQpd/QHF5FzNl+5+efqtiiqBgDANUp9Rn3hhRe0b98+1atXTzExMU7zmUliPjM3c1wdkghEAAC4SqnPqIMHD6aQ2oMc9UOhQf7y9+P3AACAK5Q6EE2bNs0N3UBJUT8EAIDrlbqGqFmzZjp69Gih5SdOnGBy1wpwMufXhzIywgwAAJcpdSDav3+/8vPzCy3PycnRDz/84JJOoXhM2wEAgOuV+Kz6n//8x/rzRx99pPDwcOt9fn6+PvnkEzVt2tS1vUMh1kMZKagGAMBlSnxWHTJkiKRzk7uOGDHCaV1gYKBiYmL0wgsvuLRzKCzr13nMmLYDAADXKXEgcsxZ1rRpU23evFmRkZFu6xSKxxUiAABcr9Rn1dTUVHf0AyXkmNiVGiIAAFynRGfVefPmafTo0QoODta8efN+t+24ceNc0jEULZOJXQEAcLkSnVXnzJmj4cOHKzg4WHPmzCm2nc1mIxC52fkrRNQQAQDgKiUKRKmpqVYNEbfMPOvkr0XV3DIDAMB1SvwcosDAQKWnp1vvJ02apGPHjrmlUyieY+qOGhRVAwDgMiUORMYYp/dLly7ViRMnXN0fXARTdwAA4HqlflK1w4UBCRXDUUNEUTUAAK5T5kAEz8ikhggAAJcr1Vl16tSpqlatmiQpNzdXTz/9tNMUHpI0e/Zs1/UOTowx50eZUUMEAIDLlPis2qNHD6WkpFjvu3btqu+//96pjc1mc13PUEh2br4cdyqpIQIAwHVKHIjWrVvnxm6gJBxD7v39bAoO5G4nAACuwlnVh1hD7oMDuBoHAIALEYh8SCYTuwIA4BYEIh/CtB0AALgHgciHWNN2cIUIAACXIhD5kN/WEAEAANcp05n1+PHjeuWVV7Rr1y5JUps2bXT33XerVq1aLu0cnDmm7eAp1QAAuFaprxAlJSWpadOmmjdvno4fP67jx49r/vz5atq0qZKSktzRR/zqZA5XiAAAcIdSn1kTEhI0dOhQLV68WP7+/pKk/Px8jRkzRgkJCdqxY4fLO4lzrBoiiqoBAHCpUl8h2rt3ryZOnGiFIUny9/fXgw8+qL1797q0c3CWxbB7AADcotSB6IorrrBqh35r165d6tChg0s6haI5aojCuGUGAIBLlfrMOm7cOI0fP1579+7VVVddJUnatGmTFi5cqJkzZ2r79u1W2/bt27uup9DJnHO3zCiqBgDAtUp9Zr3tttskSQ8//HCR62w2m4wxstlsys/PL38PYbGG3dupIQIAwJVKHYhSU1Pd0Q+UAMPuAQBwj1LXEDVp0qTEr4tJSkrSwIEDFR0dLZvNplWrVhXb9t5775XNZtOLL77otPzYsWMaPny4wsLCFBERoZEjRyorK8upzfbt29W9e3cFBwerUaNGmjVrVml32ysw7B4AAPco05Oq9+3bp/vvv1/x8fGKj4/XuHHjtG/fvlJ/TnZ2tjp06KCFCxf+brt3331XmzZtUnR0dKF1w4cP186dO5WYmKjVq1crKSlJo0ePttZnZmaqT58+atKkibZu3arnnntO06ZN00svvVTq/nra+ak7uGUGAIArlfpSw0cffaRBgwbp8ssvV7du3SRJGzZsULt27fTee+/puuuuK/Fn9e/fX/379//dNj/++KPuv/9+ffTRR7r++uud1u3atUsffvihNm/erE6dOkmS5s+frwEDBuj5559XdHS0Vq5cqdzcXP3tb39TUFCQ2rVrp+TkZM2ePdspOHm7vPwCnckrkMQVIgAAXK3UV4gmT56sCRMm6Msvv9Ts2bM1e/Zsffnll3rggQf0yCOPuLRzBQUFuuOOOzRp0iS1a9eu0PqNGzcqIiLCCkOSFB8fLz8/P3355ZdWmx49eigoKMhq07dvX6WkpOj48ePFbjsnJ0eZmZlOL09yFFRL1BABAOBqpQ5Eu3bt0siRIwstv/vuu/Xtt9+6pFMOzz77rAICAjRu3Lgi16elpalu3bpOywICAlSrVi2lpaVZberVq+fUxvHe0aYoM2bMUHh4uPVq1KhReXal3LJ+rR8KDvRToD9z8gIA4EqlPrPWqVNHycnJhZYnJycXCiflsXXrVs2dO1fLly+XzWZz2eeW1JQpU5SRkWG9Dh06VOF9+K3MX+uHqlM/BACAy5X43suTTz6phx56SKNGjdLo0aP1/fffq2vXrpLO1RA9++yzevDBB13Wsc8//1zp6elq3LixtSw/P18TJ07Uiy++qP379ysqKkrp6elOP3f27FkdO3ZMUVFRkqSoqCj99NNPTm0c7x1timK322W32121O+WWxVOqAQBwmxKfXadPn657771Xjz/+uGrUqKEXXnhBU6ZMkSRFR0dr2rRpxd7aKos77rhD8fHxTsv69u2rO+64Q3fddZckKS4uTidOnNDWrVsVGxsrSfr0009VUFCgLl26WG0ee+wx5eXlKTDw3NWVxMREtWrVSjVr1nRZf92NZxABAOA+JT67GmMkSTabTRMmTNCECRN08uRJSVKNGjXKtPGsrCynCWFTU1OVnJysWrVqqXHjxqpdu7ZT+8DAQEVFRalVq1aSpDZt2qhfv34aNWqUlixZory8PI0dO1bDhg2zhujffvvtmj59ukaOHKlHHnlE33zzjebOnas5c+aUqc+eksUziAAAcJtSnV0vrOUpaxBy2LJli3r16mW9d9xyGzFihJYvX16iz1i5cqXGjh2r3r17y8/PTzfddJPmzZtnrQ8PD9fatWuVkJCg2NhYRUZGaurUqT415F7iGUQAALhTqQLRJZdcctEC52PHjpX483r27GldeSqJ/fv3F1pWq1Yt/eMf//jdn2vfvr0+//zzEm/HG2VyywwAALcp1dl1+vTpCg8Pd1df8Du4ZQYAgPuU6uw6bNgwlw6tR8mdv2VGIAIAwNVK/BwiTzwLCOc5ht3XCKaGCAAAVytxICpNrQ9cj2H3AAC4T4nPrgUFBe7sBy7iJDVEAAC4DZNi+QjrChE1RAAAuByByEdk5fxaVE0NEQAALkcg8hEnz3DLDAAAdyEQ+QBjzG9GmRGIAABwNQKRDziTV6CzBedG+VFDBACA6xGIfIDjoYw2mxQaRCACAMDVCEQ+wDHkvro9QH5+PCATAABXIxD5AKugmttlAAC4BYHIBzBtBwAA7kUg8gGOGiKm7QAAwD0IRD6AaTsAAHAvApEPYNoOAADci0DkA6ghAgDAvQhEPsBRQ8QtMwAA3INA5AOychh2DwCAOxGIfIBVQ8QVIgAA3IJA5AMyrVtm1BABAOAOBCIfcJKZ7gEAcCsCkQ84lp0rSaodGuThngAAUDkRiHzA0awcSVItAhEAAG5BIPJyZ/LylZ2bL0mqHWr3cG8AAKicCEReznG7LMDPprAQaogAAHAHApGXO5p1LhDVCg2SzWbzcG8AAKicCERe7mg29UMAALgbgcjLOW6ZRVanfggAAHchEHm5394yAwAA7kEg8nJHswlEAAC4G4HIyx37tYYosjqBCAAAdyEQebnzt8yoIQIAwF0IRF6OW2YAALgfgcjLnR9lRiACAMBdCERejnnMAABwPwKRF2MeMwAAKgaByIsxjxkAABWDQOTFjmUzjxkAABWBQOTFfqF+CACACkEg8mLMYwYAQMUgEHmxYzyDCACACkEg8mK/MLErAAAVgkDkxZjHDACAikEg8mLnb5lRQwQAgDsRiLwYt8wAAKgYBCIvxjxmAABUDAKRF2OUGQAAFYNA5KXO5OUrK+esJOYxAwDA3QhEXop5zAAAqDgEIi/FPGYAAFQcApGXYh4zAAAqDoHISzmuENVmhBkAAG5HIPJSViCioBoAALcjEHmpowy5BwCgwhCIvNTRX2uIahOIAABwOwKRlzpfQ8QtMwAA3I1A5KW4ZQYAQMUhEHmpo1mMMgMAoKIQiLzU+VFmBCIAANyNQOSFmMcMAICKRSDyQsxjBgBAxSIQeSHmMQMAoGJ5NBAlJSVp4MCBio6Ols1m06pVq5zWT5s2Ta1bt1ZoaKhq1qyp+Ph4ffnll05tjh07puHDhyssLEwREREaOXKksrKynNps375d3bt3V3BwsBo1aqRZs2a5e9fKhRFmAABULI8GouzsbHXo0EELFy4scv0ll1yiBQsWaMeOHfriiy8UExOjPn366Oeff7baDB8+XDt37lRiYqJWr16tpKQkjR492lqfmZmpPn36qEmTJtq6dauee+45TZs2TS+99JLb96+srIcyMsIMAIAKYTPGGE93QpJsNpveffddDRkypNg2mZmZCg8P18cff6zevXtr165datu2rTZv3qxOnTpJkj788EMNGDBAP/zwg6Kjo7V48WI99thjSktLU1DQuYAxefJkrVq1Srt37y5x/xzbzsjIUFhYWLn29WJe/vx7PfX+Lg3qEK15t3V067YAAKjMSnr+9pkaotzcXL300ksKDw9Xhw4dJEkbN25URESEFYYkKT4+Xn5+ftattY0bN6pHjx5WGJKkvn37KiUlRcePHy92ezk5OcrMzHR6VRRumQEAULG8PhCtXr1a1atXV3BwsObMmaPExERFRkZKktLS0lS3bl2n9gEBAapVq5bS0tKsNvXq1XNq43jvaFOUGTNmKDw83Ho1atTIlbv1u5jHDACAiuX1gahXr15KTk7Wf//7X/Xr109Dhw5Venq627c7ZcoUZWRkWK9Dhw65fZsOzGMGAEDF8vpAFBoaqhYtWuiqq67SK6+8ooCAAL3yyiuSpKioqELh6OzZszp27JiioqKsNj/99JNTG8d7R5ui2O12hYWFOb0qCrfMAACoWF4fiC5UUFCgnJxzt5Ti4uJ04sQJbd261Vr/6aefqqCgQF26dLHaJCUlKS8vz2qTmJioVq1aqWbNmhXb+RI6f4WIQAQAQEXwaCDKyspScnKykpOTJUmpqalKTk7WwYMHlZ2drUcffVSbNm3SgQMHtHXrVt1999368ccfdcstt0iS2rRpo379+mnUqFH66quvtGHDBo0dO1bDhg1TdHS0JOn2229XUFCQRo4cqZ07d+qNN97Q3Llz9eCDD3pqty/KmtiVK0QAAFQIj84LsWXLFvXq1ct67wgpI0aM0JIlS7R79269+uqr+uWXX1S7dm1deeWV+vzzz9WuXTvrZ1auXKmxY8eqd+/e8vPz00033aR58+ZZ68PDw7V27VolJCQoNjZWkZGRmjp1qtOzirxJzlnmMQMAoKJ5zXOIvF1FPYfoSMZpxc34VAF+Nu15uj9TdwAAUA6V7jlEVYXjdhnzmAEAUHEIRF6GEWYAAFQ8ApGXOZbNPGYAAFQ0ApGXOT/CjIJqAAAqCoHIy3DLDACAikcg8jLHeAYRAAAVjkDkZY5aNUTcMgMAoKIQiLwMt8wAAKh4BCIvwzxmAABUPAKRl2EeMwAAKh6ByIswjxkAAJ5BIPIijttlAX42hYV4dN5dAACqFAKRF2EeMwAAPINA5EUYYQYAgGcQiLwI85gBAOAZBCIvwjxmAAB4BoHIi3DLDAAAzyAQeRHmMQMAwDMIRF7EukJEDREAABWKQORFrIldqSECAKBCEYi8CPOYAQDgGQQiL3Isi6JqAAA8gUDkJXLO5uvkr/OYRXLLDACACkUg8hLMYwYAgOcQiLyE46GMNZnHDACACkcg8hKOIfc8gwgAgIpHIPISzGMGAIDnEIi8xFFrhBkF1QAAVDQCkZc4xi0zAAA8hkDkJY4yjxkAAB5DIPISzGMGAIDnEIi8xDHmMQMAwGMIRF7iKPOYAQDgMQQiL8E8ZgAAeA6ByAswjxkAAJ5FIPICzGMGAIBnEYi8APOYAQDgWQQiL8BDGQEA8CwCkRc4yjxmAAB4FIHICzCPGQAAnkUg8gLcMgMAwLMIRF6AecwAAPAsApEXYB4zAAA8i0DkBZjHDAAAzyIQeYFjzGMGAIBHEYi8wFHmMQMAwKMIRB7GPGYAAHgegcjDjmfnSWIeMwAAPIlA5GG/ZJ0rqGYeMwAAPIdA5GE8lBEAAM8jEHkYI8wAAPA8ApGHOW6ZMY8ZAACeQyDyMG6ZAQDgeQQiDyMQAQDgeQQiD/sli3nMAADwNAKRhzGPGQAAnkcg8jBGmQEA4HkEIg9jHjMAADyPQORBefkFCgzwk83GPGYAAHgSk2d5UKC/n7Y9fp3yC4z8mLUDAACPIRB5AX/SEAAAHsUtMwAAUOURiAAAQJXn0UCUlJSkgQMHKjo6WjabTatWrbLW5eXl6ZFHHtFll12m0NBQRUdH609/+pMOHz7s9BnHjh3T8OHDFRYWpoiICI0cOVJZWVlObbZv367u3bsrODhYjRo10qxZsypi9wAAgI/waCDKzs5Whw4dtHDhwkLrTp06pW3btunxxx/Xtm3b9M477yglJUWDBg1yajd8+HDt3LlTiYmJWr16tZKSkjR69GhrfWZmpvr06aMmTZpo69ateu655zRt2jS99NJLbt8/AADgG2zGGOPpTkiSzWbTu+++qyFDhhTbZvPmzercubMOHDigxo0ba9euXWrbtq02b96sTp06SZI+/PBDDRgwQD/88IOio6O1ePFiPfbYY0pLS1NQ0Lln/UyePFmrVq3S7t27S9y/zMxMhYeHKyMjQ2FhYeXaVwAAUDFKev72qRqijIwM2Ww2RURESJI2btyoiIgIKwxJUnx8vPz8/PTll19abXr06GGFIUnq27evUlJSdPz48QrtPwAA8E4+M+z+zJkzeuSRR3TbbbdZCS8tLU1169Z1ahcQEKBatWopLS3NatO0aVOnNvXq1bPW1axZs8jt5eTkKCcnx3qfmZnpsn0BAADexSeuEOXl5Wno0KEyxmjx4sUVss0ZM2YoPDzcejVq1KhCtgsAACqe1wciRxg6cOCAEhMTne7/RUVFKT093an92bNndezYMUVFRVltfvrpJ6c2jveONkWZMmWKMjIyrNehQ4dctUsAAMDLeHUgcoShPXv26OOPP1bt2rWd1sfFxenEiRPaunWrtezTTz9VQUGBunTpYrVJSkpSXl6e1SYxMVGtWrUq9naZJNntdoWFhTm9AABA5eTRQJSVlaXk5GQlJydLklJTU5WcnKyDBw8qLy9PN998s7Zs2aKVK1cqPz9faWlpSktLU27uuRni27Rpo379+mnUqFH66quvtGHDBo0dO1bDhg1TdHS0JOn2229XUFCQRo4cqZ07d+qNN97Q3Llz9eCDD3pqtwEAgJfx6LD7devWqVevXoWWjxgxQtOmTStUDO3w2WefqWfPnpLOPZhx7Nixeu+99+Tn56ebbrpJ8+bNU/Xq1a3227dvV0JCgjZv3qzIyEjdf//9euSRR0rVV4bdAwDge0p6/vaa5xB5OwIRAAC+p6Tnb58Zdu9pjtzI8HsAAHyH47x9ses/BKISOnnypCQx/B4AAB908uRJhYeHF7ueW2YlVFBQoMOHD6tGjRqy2Wwu+9zMzEw1atRIhw4d4lZcBeB4VyyOd8XieFcsjnfFKuvxNsbo5MmTio6Olp9f8WPJuEJUQn5+fmrYsKHbPp+h/RWL412xON4Vi+NdsTjeFassx/v3rgw5ePVziAAAACoCgQgAAFR5BCIPs9vteuKJJ2S32z3dlSqB412xON4Vi+NdsTjeFcvdx5uiagAAUOVxhQgAAFR5BCIAAFDlEYgAAECVRyACAABVHoHIwxYuXKiYmBgFBwerS5cu+uqrrzzdpUohKSlJAwcOVHR0tGw2m1atWuW03hijqVOnqn79+goJCVF8fLz27Nnjmc76uBkzZujKK69UjRo1VLduXQ0ZMkQpKSlObc6cOaOEhATVrl1b1atX10033aSffvrJQz32bYsXL1b79u2th9PFxcVpzZo11nqOtXvNnDlTNptNDzzwgLWMY+4606ZNk81mc3q1bt3aWu/OY00g8qA33nhDDz74oJ544glt27ZNHTp0UN++fZWenu7prvm87OxsdejQQQsXLixy/axZszRv3jwtWbJEX375pUJDQ9W3b1+dOXOmgnvq+9avX6+EhARt2rRJiYmJysvLU58+fZSdnW21mTBhgt577z29+eabWr9+vQ4fPqwbb7zRg732XQ0bNtTMmTO1detWbdmyRddee60GDx6snTt3SuJYu9PmzZu1dOlStW/f3mk5x9y12rVrpyNHjlivL774wlrn1mNt4DGdO3c2CQkJ1vv8/HwTHR1tZsyY4cFeVT6SzLvvvmu9LygoMFFRUea5556zlp04ccLY7Xbzz3/+0wM9rFzS09ONJLN+/XpjzLljGxgYaN58802rza5du4wks3HjRk91s1KpWbOmefnllznWbnTy5EnTsmVLk5iYaK655hozfvx4Ywzfb1d74oknTIcOHYpc5+5jzRUiD8nNzdXWrVsVHx9vLfPz81N8fLw2btzowZ5VfqmpqUpLS3M69uHh4erSpQvH3gUyMjIkSbVq1ZIkbd26VXl5eU7Hu3Xr1mrcuDHHu5zy8/P1+uuvKzs7W3FxcRxrN0pISND111/vdGwlvt/usGfPHkVHR6tZs2YaPny4Dh48KMn9x5rJXT3kl19+UX5+vurVq+e0vF69etq9e7eHelU1pKWlSVKRx96xDmVTUFCgBx54QN26ddOll14q6dzxDgoKUkREhFNbjnfZ7dixQ3FxcTpz5oyqV6+ud999V23btlVycjLH2g1ef/11bdu2TZs3by60ju+3a3Xp0kXLly9Xq1atdOTIEU2fPl3du3fXN9984/ZjTSAC4DIJCQn65ptvnO75w/VatWql5ORkZWRk6K233tKIESO0fv16T3erUjp06JDGjx+vxMREBQcHe7o7lV7//v2tP7dv315dunRRkyZN9K9//UshISFu3Ta3zDwkMjJS/v7+harjf/rpJ0VFRXmoV1WD4/hy7F1r7NixWr16tT777DM1bNjQWh4VFaXc3FydOHHCqT3Hu+yCgoLUokULxcbGasaMGerQoYPmzp3LsXaDrVu3Kj09XVdccYUCAgIUEBCg9evXa968eQoICFC9evU45m4UERGhSy65RHv37nX795tA5CFBQUGKjY3VJ598Yi0rKCjQJ598ori4OA/2rPJr2rSpoqKinI59ZmamvvzyS459GRhjNHbsWL377rv69NNP1bRpU6f1sbGxCgwMdDreKSkpOnjwIMfbRQoKCpSTk8OxdoPevXtrx44dSk5Otl6dOnXS8OHDrT9zzN0nKytL+/btU/369d3//S53WTbK7PXXXzd2u90sX77cfPvtt2b06NEmIiLCpKWlebprPu/kyZPm66+/Nl9//bWRZGbPnm2+/vprc+DAAWOMMTNnzjQRERHm3//+t9m+fbsZPHiwadq0qTl9+rSHe+577rvvPhMeHm7WrVtnjhw5Yr1OnTpltbn33ntN48aNzaeffmq2bNli4uLiTFxcnAd77bsmT55s1q9fb1JTU8327dvN5MmTjc1mM2vXrjXGcKwrwm9HmRnDMXeliRMnmnXr1pnU1FSzYcMGEx8fbyIjI016eroxxr3HmkDkYfPnzzeNGzc2QUFBpnPnzmbTpk2e7lKl8NlnnxlJhV4jRowwxpwbev/444+bevXqGbvdbnr37m1SUlI822kfVdRxlmSWLVtmtTl9+rQZM2aMqVmzpqlWrZq54YYbzJEjRzzXaR929913myZNmpigoCBTp04d07t3bysMGcOxrggXBiKOuevceuutpn79+iYoKMg0aNDA3HrrrWbv3r3Wencea5sxxpT/OhMAAIDvooYIAABUeQQiAABQ5RGIAABAlUcgAgAAVR6BCAAAVHkEIgAAUOURiAAAQJVHIAKAcli+fHmh2bcB+B4CEYAKkZaWpvHjx6tFixYKDg5WvXr11K1bNy1evFinTp3ydPdKJCYmRi+++KLTsltvvVXfffedZzoEwGUCPN0BAJXf999/r27duikiIkLPPPOMLrvsMtntdu3YsUMvvfSSGjRooEGDBnmkb8YY5efnKyCgbP8choSEKCQkxMW9AlDRuEIEwO3GjBmjgIAAbdmyRUOHDlWbNm3UrFkzDR48WO+//74GDhwoSTpx4oTuuece1alTR2FhYbr22mv1v//9z/qcadOm6fLLL9eKFSsUExOj8PBwDRs2TCdPnrTaFBQUaMaMGWratKlCQkLUoUMHvfXWW9b6devWyWazac2aNYqNjZXdbtcXX3yhffv2afDgwapXr56qV6+uK6+8Uh9//LH1cz179tSBAwc0YcIE2Ww22Ww2SUXfMlu8eLGaN2+uoKAgtWrVSitWrHBab7PZ9PLLL+uGG25QtWrV1LJlS/3nP/+x1h8/flzDhw9XnTp1FBISopYtW2rZsmXl/0UAKBaBCIBbHT16VGvXrlVCQoJCQ0OLbOMIF7fccovS09O1Zs0abd26VVdccYV69+6tY8eOWW337dunVatWafXq1Vq9erXWr1+vmTNnWutnzJih1157TUuWLNHOnTs1YcIE/fGPf9T69eudtjl58mTNnDlTu3btUvv27ZWVlaUBAwbok08+0ddff61+/fpp4MCBOnjwoCTpnXfeUcOGDfXkk0/qyJEjOnLkSJH78u6772r8+PGaOHGivvnmG/35z3/WXXfdpc8++8yp3fTp0zV06FBt375dAwYM0PDhw639fPzxx/Xtt99qzZo12rVrlxYvXqzIyMhSHnkApeKSKWIBoBibNm0yksw777zjtLx27domNDTUhIaGmocffth8/vnnJiwszJw5c8apXfPmzc3SpUuNMcY88cQTplq1aiYzM9NaP2nSJNOlSxdjjDFnzpwx1apVM//973+dPmPkyJHmtttuM8YY89lnnxlJZtWqVRfte7t27cz8+fOt902aNDFz5sxxarNs2TITHh5uve/atasZNWqUU5tbbrnFDBgwwHovyfzf//2f9T4rK8tIMmvWrDHGGDNw4EBz1113XbR/AFyHGiIAHvHVV1+poKBAw4cPV05Ojv73v/8pKytLtWvXdmp3+vRp7du3z3ofExOjGjVqWO/r16+v9PR0SdLevXt16tQpXXfddU6fkZubq44dOzot69Spk9P7rKwsTZs2Te+//76OHDmis2fP6vTp09YVopLatWuXRo8e7bSsW7dumjt3rtOy9u3bW38ODQ1VWFiYtR/33XefbrrpJm3btk19+vTRkCFD1LVr11L1A0DpEIgAuFWLFi1ks9mUkpLitLxZs2aSZBUkZ2VlqX79+lq3bl2hz/htjU5gYKDTOpvNpoKCAuszJOn9999XgwYNnNrZ7Xan9xfevnvooYeUmJio559/Xi1atFBISIhuvvlm5ebmlnBPS+f39qN///46cOCAPvjgAyUmJqp3795KSEjQ888/75a+ACAQAXCz2rVr67rrrtOCBQt0//33F1tHdMUVVygtLU0BAQGKiYkp07batm0ru92ugwcP6pprrinVz27YsEF33nmnbrjhBknnwtX+/fud2gQFBSk/P/93P6dNmzbasGGDRowY4fTZbdu2LVV/6tSpoxEjRmjEiBHq3r27Jk2aRCAC3IhABMDtFi1apG7duqlTp06aNm2a2rdvLz8/P23evFm7d+9WbGys4uPjFRcXpyFDhmjWrFm65JJLdPjwYb3//vu64YYbCt3iKkqNGjX00EMPacKECSooKNDVV1+tjIwMbdiwQWFhYU4h5UItW7bUO++8o4EDB8pms+nxxx+3rtg4xMTEKCkpScOGDZPdbi+y0HnSpEkaOnSoOnbsqPj4eL333nt65513nEasXczUqVMVGxurdu3aKScnR6tXr1abNm1K/PMASo9ABMDtmjdvrq+//lrPPPOMpkyZoh9++EF2u11t27bVQw89pDFjxshms+mDDz7QY489prvuuks///yzoqKi1KNHD9WrV6/E2/rLX/6iOnXqaMaMGfr+++8VERGhK664Qo8++ujv/tzs2bN19913q2vXroqMjNQjjzyizMxMpzZPPvmk/vznP6t58+bKycmRMabQ5wwZMkRz587V888/r/Hjx6tp06ZatmyZevbsWeJ9CAoK0pQpU7R//36FhISoe/fuev3110v88wBKz2aK+hsNAABQhfAcIgAAUOURiAAAQJVHIAIAAFUegQgAAFR5BCIAAFDlEYgAAECVRyACAABVHoEIAABUeQQiAABQ5RGIAABAlUcgAgAAVR6BCAAAVHn/D4Mo1k83xk6WAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "from random import randint\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "knapsack_threshold = 35  # Maximum weight that the bag of thief can hold \n",
    "\n",
    "# 1. Initialize items with random values.\n",
    "goods = [(random.randint(1, 12), random.randint(10, 512)) for i in range(10)]\n",
    "weight = np.array([item[0] for item in goods])\n",
    "value = np.array([item[1] for item in goods])\n",
    "\n",
    "# 2. Display items: ID, weight, and worth.\n",
    "print(\"Item ID\\tWeight\\tWorth\")\n",
    "for idx, (wgt, worth) in enumerate(goods):\n",
    "    print(f\"{idx+1}\\t{wgt}\\t{worth}\")\n",
    "\n",
    "# 3. Generate the initial population.\n",
    "solutions_per_pop = 10\n",
    "pop_size = (solutions_per_pop, len(goods))\n",
    "initial_population = np.random.randint(2, size=pop_size)\n",
    "initial_population = initial_population.astype(int)\n",
    "\n",
    "# 4. Show the starting population.\n",
    "print('Initial population: \\n{}'.format(initial_population))\n",
    "\n",
    "# 5. Calculate fitness of a gene sequence.\n",
    "def cal_fitness(weight, value, population, threshold):\n",
    "    fitness = np.empty(population.shape[0])\n",
    "    for i in range(population.shape[0]):\n",
    "        S1 = np.sum(population[i] * value)\n",
    "        S2 = np.sum(population[i] * weight)\n",
    "        if S2 <= threshold:\n",
    "            fitness[i] = S1\n",
    "        else:\n",
    "            fitness[i] = 0 \n",
    "    return fitness.astype(int) \n",
    "\n",
    "# 6. Choose fittest gene sequences as parents.\n",
    "def selection(fitness, num_parents, population):\n",
    "    fitness = list(fitness)\n",
    "    parents = np.empty((num_parents, population.shape[1]))\n",
    "    for i in range(num_parents):\n",
    "        max_fitness_idx = np.where(fitness == np.max(fitness))\n",
    "        parents[i, :] = population[max_fitness_idx[0][0], :]\n",
    "        fitness[max_fitness_idx[0][0]] = -999999\n",
    "    return parents\n",
    "\n",
    "# 7. Apply one-point crossover.\n",
    "def crossover(parents, num_offsprings):\n",
    "    offsprings = np.empty((num_offsprings, parents.shape[1]))\n",
    "    crossover_point = np.random.randint(1, parents.shape[1])\n",
    "    for i in range(num_offsprings):\n",
    "        parent1_index = i % parents.shape[0]\n",
    "        parent2_index = (i+1) % parents.shape[0]\n",
    "        offsprings[i, 0:crossover_point] = parents[parent1_index, 0:crossover_point]\n",
    "        offsprings[i, crossover_point:] = parents[parent2_index, crossover_point:]\n",
    "    return offsprings\n",
    "\n",
    "# 8. Introduce potential mutations.\n",
    "def mutation(offsprings):\n",
    "    mutants = np.empty((offsprings.shape))\n",
    "    mutation_rate = 0.4\n",
    "    for i in range(mutants.shape[0]):\n",
    "        random_value = random.random()\n",
    "        mutants[i, :] = offsprings[i, :]\n",
    "        if random_value > mutation_rate:\n",
    "            continue\n",
    "        int_random_value = randint(0, offsprings.shape[1]-1)    \n",
    "        if mutants[i, int_random_value] == 0:\n",
    "            mutants[i, int_random_value] = 1\n",
    "        else:\n",
    "            mutants[i, int_random_value] = 0\n",
    "    return mutants\n",
    "\n",
    "# 9. Iterate through the GA process.\n",
    "top_fitnesses = []\n",
    "pop_members = initial_population\n",
    "\n",
    "for generation in range(50):\n",
    "    fitness = cal_fitness(weight, value, pop_members, knapsack_threshold)\n",
    "    num_parents = pop_size[0] // 2\n",
    "    num_offsprings = pop_size[0] - num_parents \n",
    "    parents = selection(fitness, num_parents, pop_members)\n",
    "    offsprings = crossover(parents, num_offsprings)\n",
    "    mutants = mutation(offsprings)\n",
    "    pop_members[0:parents.shape[0], :] = parents\n",
    "    pop_members[parents.shape[0]:, :] = mutants\n",
    "    top_fitnesses.append(np.max(fitness))\n",
    "\n",
    "# 10. Present the chosen items.\n",
    "item_number = np.arange(1, len(goods) + 1)\n",
    "fitness_last_gen = cal_fitness(weight, value, pop_members, knapsack_threshold)\n",
    "max_fitness = np.where(fitness_last_gen == np.max(fitness_last_gen))\n",
    "parameters = pop_members[max_fitness[0][0], :]\n",
    "\n",
    "print('\\nSelected items that will maximize the knapsack without breaking it:')\n",
    "selected_items = item_number * parameters\n",
    "for item in selected_items:\n",
    "    if item != 0:\n",
    "        print(item)\n",
    "\n",
    "# 11. Plot fitness evolution across generations.\n",
    "plt.plot(top_fitnesses)\n",
    "plt.title('Top Fitness through the generations')\n",
    "plt.xlabel('Generations')\n",
    "plt.ylabel('Top Fitness')\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "79b8cb7c-c4c6-41fc-af74-afd3af47dbcf",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fcab01ff-b15c-4a5d-a603-3fa5d26d4138",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "25d92c04-f8d9-4846-8ea0-9570de6fbb86",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "prac",
   "language": "python",
   "name": "prac"
  },
  "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.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}