report.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Лабораторная работа №2. Задача о рюкзаке 0-1\n",
    "Илья Седунов, <br>\n",
    "Вадим Альперович, <br>\n",
    "17ПМИ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "--- \n",
    "\n",
    "\n",
    "## Knapsack 01\n",
    " - capacity: *165*<br>\n",
    " - optimal solution: ```[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]```<br>\n",
    " - optimal weight: *165*, and profit: *309*<br>\n",
    "   **BruteForce** optimal solution: ```[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]```<br>\n",
    "          optimal weight: 165, and profit **309**\n",
    "   **Greedy** optimal solution: ```[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]```<br>\n",
    "          optimal weight: 165, and profit **309**\n",
    "   **Branch-And-Bound** optimal solution: ```[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]```<br>\n",
    "          optimal weight: 165, and profit **309**\n",
    "   **Dynamic** optimal solution: ```[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]```<br>\n",
    "          optimal weight: 165, and profit **309**\n",
    "   **Genetic** optimal solution: ```[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]```<br>\n",
    "          optimal weight: 165, and profit **309**\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack 02\n",
    " - capacity: *26*<br>\n",
    " - optimal solution: ```[0, 1, 1, 1, 0]```<br>\n",
    " - optimal weight: *26*, and profit: *51*<br>\n",
    "   **BruteForce** optimal solution: ```[0, 1, 1, 1, 0]```<br>\n",
    "          optimal weight: 26, and profit **51**\n",
    "   **Greedy** optimal solution: ```[1, 0, 1, 0, 0]```<br>\n",
    "          optimal weight: 23, and profit **47**\n",
    "   **Branch-And-Bound** optimal solution: ```[0, 1, 1, 1, 0]```<br>\n",
    "          optimal weight: 26, and profit **51**\n",
    "   **Dynamic** optimal solution: ```[0, 1, 1, 1, 0]```<br>\n",
    "          optimal weight: 26, and profit **51**\n",
    "   **Genetic** optimal solution: ```[0, 1, 1, 1, 0]```<br>\n",
    "          optimal weight: 26, and profit **51**\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack 03\n",
    " - capacity: *190*<br>\n",
    " - optimal solution: ```[1, 1, 0, 0, 1, 0]```<br>\n",
    " - optimal weight: *190*, and profit: *150*<br>\n",
    "   **BruteForce** optimal solution: ```[1, 1, 0, 0, 1, 0]```<br>\n",
    "          optimal weight: 190, and profit **150**\n",
    "   **Greedy** optimal solution: ```[1, 1, 0, 1, 0, 0]```<br>\n",
    "          optimal weight: 179, and profit **146**\n",
    "   **Branch-And-Bound** optimal solution: ```[1, 1, 0, 0, 1, 0]```<br>\n",
    "          optimal weight: 190, and profit **150**\n",
    "   **Dynamic** optimal solution: ```[1, 1, 0, 0, 1, 0]```<br>\n",
    "          optimal weight: 190, and profit **150**\n",
    "   **Genetic** optimal solution: ```[1, 0, 1, 0, 0, 1]```<br>\n",
    "          optimal weight: 153, and profit **119**\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack 04\n",
    " - capacity: *50*<br>\n",
    " - optimal solution: ```[1, 0, 0, 1, 0, 0, 0]```<br>\n",
    " - optimal weight: *50*, and profit: *107*<br>\n",
    "   **BruteForce** optimal solution: ```[1, 0, 0, 1, 0, 0, 0]```<br>\n",
    "          optimal weight: 50, and profit **107**\n",
    "   **Greedy** optimal solution: ```[1, 1, 0, 0, 1, 1, 0]```<br>\n",
    "          optimal weight: 48, and profit **102**\n",
    "   **Branch-And-Bound** optimal solution: ```[1, 0, 0, 1, 0, 0, 0]```<br>\n",
    "          optimal weight: 50, and profit **107**\n",
    "   **Dynamic** optimal solution: ```[1, 0, 0, 1, 0, 0, 0]```<br>\n",
    "          optimal weight: 50, and profit **107**\n",
    "   **Genetic** optimal solution: ```[1, 1, 0, 0, 0, 1, 1]```<br>\n",
    "          optimal weight: 50, and profit **105**\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack 05\n",
    " - capacity: *104*<br>\n",
    " - optimal solution: ```[1, 0, 1, 1, 1, 0, 1, 1]```<br>\n",
    " - optimal weight: *104*, and profit: *900*<br>\n",
    "   **BruteForce** optimal solution: ```[1, 0, 1, 1, 1, 0, 1, 1]```<br>\n",
    "          optimal weight: 104, and profit **900**\n",
    "   **Greedy** optimal solution: ```[1, 1, 0, 1, 1, 1, 1, 1]```<br>\n",
    "          optimal weight: 97, and profit **858**\n",
    "   **Branch-And-Bound** optimal solution: ```[1, 0, 1, 1, 1, 0, 1, 1]```<br>\n",
    "          optimal weight: 104, and profit **900**\n",
    "   **Dynamic** optimal solution: ```[1, 0, 1, 1, 1, 0, 1, 1]```<br>\n",
    "          optimal weight: 104, and profit **900**\n",
    "   **Genetic** optimal solution: ```[1, 0, 1, 1, 1, 0, 1, 1]```<br>\n",
    "          optimal weight: 104, and profit **900**\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack 06\n",
    " - capacity: *170*<br>\n",
    " - optimal solution: ```[0, 1, 0, 1, 0, 0, 1]```<br>\n",
    " - optimal weight: *169*, and profit: *1735*<br>\n",
    "   **BruteForce** optimal solution: ```[0, 1, 0, 1, 0, 0, 1]```<br>\n",
    "          optimal weight: 169, and profit **1735**\n",
    "   **Greedy** optimal solution: ```[1, 1, 1, 0, 0, 0, 0]```<br>\n",
    "          optimal weight: 140, and profit **1478**\n",
    "   **Branch-And-Bound** optimal solution: ```[0, 1, 0, 1, 0, 0, 1]```<br>\n",
    "          optimal weight: 169, and profit **1735**\n",
    "   **Dynamic** optimal solution: ```[0, 1, 0, 1, 0, 0, 1]```<br>\n",
    "          optimal weight: 169, and profit **1735**\n",
    "   **Genetic** optimal solution: ```[0, 1, 0, 1, 0, 0, 1]```<br>\n",
    "          optimal weight: 169, and profit **1735**\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack 07\n",
    " - capacity: *750*<br>\n",
    " - optimal solution: ```[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]```<br>\n",
    " - optimal weight: *749*, and profit: *1458*<br>\n",
    "   **BruteForce** optimal solution: ```[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]```<br>\n",
    "          optimal weight: 749, and profit **1458**\n",
    "   **Greedy** optimal solution: ```[1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]```<br>\n",
    "          optimal weight: 740, and profit **1441**\n",
    "   **Branch-And-Bound** optimal solution: ```[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]```<br>\n",
    "          optimal weight: 749, and profit **1458**\n",
    "   **Dynamic** optimal solution: ```[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]```<br>\n",
    "          optimal weight: 749, and profit **1458**\n",
    "   **Genetic** optimal solution: ```[1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]```<br>\n",
    "          optimal weight: 749, and profit **1458**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center> Low-dimension knapsnacks</center>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f10_l-d_kp_20_879\n",
    " - capacity: *879*<br>\n",
    " - optimal profit: *1025*<br>\n",
    "   **Greedy** optimal solution: ```[1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 837, and profit **1019**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 0.0, 1.0, 1.0, 1.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.06s```<br>\n",
    "     optimal weight: 871.0, and profit **1025.0**<br>\n",
    "   **Dynamic** optimal solution: ```[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1]```<br>\n",
    "  **Dynamic**  ```exec time 0.09s```<br>\n",
    "     optimal weight: 871, and profit **1025**<br>\n",
    "   **Genetic** optimal solution: ```[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1]```<br>\n",
    "  **Genetic**  ```exec time 0.80s```<br>\n",
    "     optimal weight: 871, and profit **1025**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f1_l-d_kp_10_269\n",
    " - capacity: *269*<br>\n",
    " - optimal profit: *295*<br>\n",
    "   **Greedy** optimal solution: ```[0, 1, 1, 0, 1, 0, 0, 1, 1, 1]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 260, and profit **294**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[0.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.05s```<br>\n",
    "     optimal weight: 269.0, and profit **295.0**<br>\n",
    "   **Dynamic** optimal solution: ```[0, 1, 1, 1, 0, 0, 0, 1, 1, 1]```<br>\n",
    "  **Dynamic**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 269, and profit **295**<br>\n",
    "   **Genetic** optimal solution: ```[0, 1, 1, 1, 0, 0, 0, 1, 1, 1]```<br>\n",
    "  **Genetic**  ```exec time 0.04s```<br>\n",
    "     optimal weight: 269, and profit **295**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f2_l-d_kp_20_878\n",
    " - capacity: *878*<br>\n",
    " - optimal profit: *1024*<br>\n",
    "   **Greedy** optimal solution: ```[1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 837, and profit **1018**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 1.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.15s```<br>\n",
    "     optimal weight: 871.0, and profit **1024.0**<br>\n",
    "   **Dynamic** optimal solution: ```[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1]```<br>\n",
    "  **Dynamic**  ```exec time 0.19s```<br>\n",
    "     optimal weight: 871, and profit **1024**<br>\n",
    "   **Genetic** optimal solution: ```[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1]```<br>\n",
    "  **Genetic**  ```exec time 1.18s```<br>\n",
    "     optimal weight: 871, and profit **1024**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f3_l-d_kp_4_20\n",
    " - capacity: *20*<br>\n",
    " - optimal profit: *35*<br>\n",
    "   **Greedy** optimal solution: ```[1, 1, 0, 1]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 18, and profit **35**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[1.0, 1.0, 0.0, 1.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 18.0, and profit **35.0**<br>\n",
    "   **Dynamic** optimal solution: ```[1, 1, 0, 1]```<br>\n",
    "  **Dynamic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 18, and profit **35**<br>\n",
    "   **Genetic** optimal solution: ```[1, 1, 0, 1]```<br>\n",
    "  **Genetic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 18, and profit **35**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f4_l-d_kp_4_11\n",
    " - capacity: *11*<br>\n",
    " - optimal profit: *23*<br>\n",
    "   **Greedy** optimal solution: ```[1, 1, 0, 0]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 6, and profit **16**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[0.0, 1.0, 0.0, 1.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.01s```<br>\n",
    "     optimal weight: 11.0, and profit **23.0**<br>\n",
    "   **Dynamic** optimal solution: ```[0, 1, 0, 1]```<br>\n",
    "  **Dynamic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 11, and profit **23**<br>\n",
    "   **Genetic** optimal solution: ```[0, 1, 1, 0]```<br>\n",
    "  **Genetic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 10, and profit **22**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f6_l-d_kp_10_60\n",
    " - capacity: *60*<br>\n",
    " - optimal profit: *52*<br>\n",
    "   **Greedy** optimal solution: ```[0, 0, 1, 0, 1, 1, 1, 1, 1, 1]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 57, and profit **52**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[0.0, 0.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 57.0, and profit **52.0**<br>\n",
    "   **Dynamic** optimal solution: ```[0, 0, 1, 1, 1, 0, 1, 0, 0, 0]```<br>\n",
    "  **Dynamic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 60, and profit **52**<br>\n",
    "   **Genetic** optimal solution: ```[0, 0, 1, 0, 1, 1, 1, 1, 1, 1]```<br>\n",
    "  **Genetic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 57, and profit **52**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f7_l-d_kp_7_50\n",
    " - capacity: *50*<br>\n",
    " - optimal profit: *107*<br>\n",
    "   **Greedy** optimal solution: ```[1, 1, 0, 0, 1, 1, 0]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 48, and profit **102**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[1.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.01s```<br>\n",
    "     optimal weight: 50.0, and profit **107.0**<br>\n",
    "   **Dynamic** optimal solution: ```[1, 0, 0, 1, 0, 0, 0]```<br>\n",
    "  **Dynamic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 50, and profit **107**<br>\n",
    "   **Genetic** optimal solution: ```[1, 0, 0, 1, 0, 0, 0]```<br>\n",
    "  **Genetic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 50, and profit **107**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f8_l-d_kp_23_10000\n",
    " - capacity: *10000*<br>\n",
    " - optimal profit: *9767*<br>\n",
    "   **Greedy** optimal solution: ```[1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 9750, and profit **9751**<br>\n",
    "   **Branch-And-Bound**    \n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 228.01s```<br>\n",
    "   **Dynamic** optimal solution: ```[1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0]```<br>\n",
    "  **Dynamic**  ```exec time 0.56s```<br>\n",
    "     optimal weight: 9768, and profit **9767**<br>\n",
    "   **Genetic** optimal solution: ```[1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0]```<br>\n",
    "  **Genetic**  ```exec time 0.74s```<br>\n",
    "     optimal weight: 9765, and profit **9764**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack f9_l-d_kp_5_80\n",
    " - capacity: *80*<br>\n",
    " - optimal profit: *130*<br>\n",
    "   **Greedy** optimal solution: ```[1, 1, 1, 1, 0]```<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 60, and profit **130**<br>\n",
    "   **Branch-And-Bound** optimal solution: ```[1.0, 1.0, 1.0, 1.0, 0.0]```<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 60.0, and profit **130.0**<br>\n",
    "   **Dynamic** optimal solution: ```[1, 1, 1, 1, 0]```<br>\n",
    "  **Dynamic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 60, and profit **130**<br>\n",
    "   **Genetic** optimal solution: ```[1, 0, 1, 1, 1]```<br>\n",
    "  **Genetic**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 71, and profit **118**<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center> Large-scale knapsnacks</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_1_1000_1000_1\n",
    " - capacity: *5002*<br>\n",
    " - optimal weight: *5002*, optimal profit: *54503*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 4991, and profit **54386**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 229.80s```<br>\n",
    "  **Dynamic**  ```exec time 14.89s```<br>\n",
    "     optimal weight: 5002, and profit **54503**<br>\n",
    "  **Genetic**  ```exec time 37.74s```<br>\n",
    "     optimal weight: 4431, and profit **9319**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_1_100_1000_1\n",
    " - capacity: *995*<br>\n",
    " - optimal weight: *985*, optimal profit: *9147*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 908, and profit **8817**<br>\n",
    "  **Branch-And-Bound**  ```exec time 2.71s```<br>\n",
    "     optimal weight: 985.0, and profit **9147.0**<br>\n",
    "  **Dynamic**  ```exec time 0.19s```<br>\n",
    "     optimal weight: 985, and profit **9147**<br>\n",
    "  **Genetic**  ```exec time 3.43s```<br>\n",
    "     optimal weight: 984, and profit **3892**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_1_2000_1000_1\n",
    " - capacity: *10011*<br>\n",
    " - optimal weight: *10011*, optimal profit: *110625*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 9996, and profit **110547**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 472.64s```<br>\n",
    "  **Dynamic**  ```exec time 61.41s```<br>\n",
    "     optimal weight: 10011, and profit **110625**<br>\n",
    "  **Genetic**  ```exec time 70.20s```<br>\n",
    "     optimal weight: 9443, and profit **14607**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_1_200_1000_1\n",
    " - capacity: *1008*<br>\n",
    " - optimal weight: *987*, optimal profit: *11238*<br>\n",
    "  **Greedy**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 981, and profit **11227**<br>\n",
    "  **Branch-And-Bound**  ```exec time 10.17s```<br>\n",
    "     optimal weight: 987.0, and profit **11238.0**<br>\n",
    "  **Dynamic**  ```exec time 0.40s```<br>\n",
    "     optimal weight: 987, and profit **11238**<br>\n",
    "  **Genetic**  ```exec time 6.79s```<br>\n",
    "     optimal weight: 960, and profit **4239**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_1_5000_1000_1\n",
    " - capacity: *25016*<br>\n",
    " - optimal weight: *25016*, optimal profit: *276457*<br>\n",
    "  **Greedy**  ```exec time 0.01s```<br>\n",
    "     optimal weight: 25008, and profit **276379**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 548.42s```<br>\n",
    "  **Dynamic**  ```exec time 407.23s```<br>\n",
    "     optimal weight: 25016, and profit **276457**<br>\n",
    "  **Genetic**  ```exec time 185.94s```<br>\n",
    "     optimal weight: 24796, and profit **24169**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_1_500_1000_1\n",
    " - capacity: *2543*<br>\n",
    " - optimal weight: *2543*, optimal profit: *28857*<br>\n",
    "  **Greedy**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 2528, and profit **28834**<br>\n",
    "  **Branch-And-Bound**  ```exec time 25.33s```<br>\n",
    "     optimal weight: 2543.0, and profit **28857.0**<br>\n",
    "  **Dynamic**  ```exec time 3.11s```<br>\n",
    "     optimal weight: 2543, and profit **28857**<br>\n",
    "  **Genetic**  ```exec time 18.08s```<br>\n",
    "     optimal weight: 2541, and profit **7810**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_2_1000_1000_1\n",
    " - capacity: *5002*<br>\n",
    " - optimal weight: *5002*, optimal profit: *9052*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 4994, and profit **9046**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 265.41s```<br>\n",
    "  **Dynamic**  ```exec time 11.92s```<br>\n",
    "     optimal weight: 5002, and profit **9052**<br>\n",
    "  **Genetic**  ```exec time 35.06s```<br>\n",
    "     optimal weight: 4997, and profit **5481**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_2_100_1000_1\n",
    " - capacity: *995*<br>\n",
    " - optimal weight: *991*, optimal profit: *1514*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 983, and profit **1487**<br>\n",
    "  **Branch-And-Bound**  ```exec time 8.25s```<br>\n",
    "     optimal weight: 991.0, and profit **1514.0**<br>\n",
    "  **Dynamic**  ```exec time 0.15s```<br>\n",
    "     optimal weight: 991, and profit **1514**<br>\n",
    "  **Genetic**  ```exec time 3.73s```<br>\n",
    "     optimal weight: 951, and profit **1265**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_2_2000_1000_1\n",
    " - capacity: *10011*<br>\n",
    " - optimal weight: *10010*, optimal profit: *18051*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 10010, and profit **18038**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 419.24s```<br>\n",
    "  **Dynamic**  ```exec time 47.54s```<br>\n",
    "     optimal weight: 10010, and profit **18051**<br>\n",
    "  **Genetic**  ```exec time 80.08s```<br>\n",
    "     optimal weight: 9889, and profit **10288**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_2_200_1000_1\n",
    " - capacity: *1008*<br>\n",
    " - optimal weight: *1006*, optimal profit: *1634*<br>\n",
    "  **Greedy**  ```exec time 0.03s```<br>\n",
    "     optimal weight: 1004, and profit **1604**<br>\n",
    "  **Branch-And-Bound**  ```exec time 52.73s```<br>\n",
    "     optimal weight: 1006.0, and profit **1634.0**<br>\n",
    "  **Dynamic**  ```exec time 0.39s```<br>\n",
    "     optimal weight: 1006, and profit **1634**<br>\n",
    "  **Genetic**  ```exec time 7.46s```<br>\n",
    "     optimal weight: 987, and profit **1270**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_2_5000_1000_1\n",
    " - capacity: *25016*<br>\n",
    " - optimal weight: *25016*, optimal profit: *44356*<br>\n",
    "  **Greedy**  ```exec time 0.01s```<br>\n",
    "     optimal weight: 25016, and profit **44351**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 482.38s```<br>\n",
    "  **Dynamic**  ```exec time 311.41s```<br>\n",
    "     optimal weight: 25016, and profit **44356**<br>\n",
    "  **Genetic**  ```exec time 193.92s```<br>\n",
    "     optimal weight: 24042, and profit **24708**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_2_500_1000_1\n",
    " - capacity: *2543*<br>\n",
    " - optimal weight: *2543*, optimal profit: *4566*<br>\n",
    "  **Greedy**  ```exec time 0.13s```<br>\n",
    "     optimal weight: 2538, and profit **4552**<br>\n",
    "  **Branch-And-Bound**  ```exec time 105.44s```<br>\n",
    "     optimal weight: 2543.0, and profit **4566.0**<br>\n",
    "  **Dynamic**  ```exec time 2.74s```<br>\n",
    "     optimal weight: 2543, and profit **4566**<br>\n",
    "  **Genetic**  ```exec time 20.31s```<br>\n",
    "     optimal weight: 2521, and profit **2874**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_3_1000_1000_1\n",
    " - capacity: *4990*<br>\n",
    " - optimal weight: *4990*, optimal profit: *14390*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 4974, and profit **14374**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 229.42s```<br>\n",
    "  **Dynamic**  ```exec time 10.98s```<br>\n",
    "     optimal weight: 4990, and profit **14390**<br>\n",
    "  **Genetic**  ```exec time 42.87s```<br>\n",
    "     optimal weight: 4963, and profit **6863**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_3_100_1000_1\n",
    " - capacity: *997*<br>\n",
    " - optimal weight: *997*, optimal profit: *2397*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 975, and profit **2375**<br>\n",
    "  **Branch-And-Bound**  ```exec time 5.85s```<br>\n",
    "     optimal weight: 997.0, and profit **2397.0**<br>\n",
    "  **Dynamic**  ```exec time 0.19s```<br>\n",
    "     optimal weight: 997, and profit **2397**<br\n",
    "  **Genetic**  ```exec time 4.22s```<br>\n",
    "     optimal weight: 970, and profit **1470**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_3_2000_1000_1\n",
    " - capacity: *9819*<br>\n",
    " - optimal weight: *9819*, optimal profit: *28919*<br>\n",
    "  **Greedy**  ```exec time 0.00s```<br>\n",
    "     optimal weight: 9727, and profit **28827**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 423.94s```<br>\n",
    "  **Dynamic**  ```exec time 47.75s```<br>\n",
    "     optimal weight: 9819, and profit **28919**<br>\n",
    "  **Genetic**  ```exec time 84.89s```<br>\n",
    "     optimal weight: 9650, and profit **12150**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_3_200_1000_1\n",
    " - capacity: *997*<br>\n",
    " - optimal weight: *997*, optimal profit: *2697*<br>\n",
    "  **Greedy**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 949, and profit **2649**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 228.41s```<br>\n",
    "  **Dynamic**  ```exec time 0.33s```<br>\n",
    "     optimal weight: 997, and profit **2697**<br>\n",
    "  **Genetic**  ```exec time 8.55s```<br>\n",
    "     optimal weight: 993, and profit **1493**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_3_5000_1000_1\n",
    " - capacity: *24805*<br>\n",
    " - optimal weight: *24805*, optimal profit: *72505*<br>\n",
    "  **Greedy**  ```exec time 0.01s```<br>\n",
    "     optimal weight: 24746, and profit **72446**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 478.12s```<br>\n",
    "  **Dynamic**  ```exec time 289.82s```<br>\n",
    "     optimal weight: 24805, and profit **72505**<br>\n",
    "  **Genetic**  ```exec time 219.38s```<br>\n",
    "     optimal weight: 23471, and profit **29671**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_3_500_1000_1\n",
    " - capacity: *2517*<br>\n",
    " - optimal weight: *2517*, optimal profit: *7117*<br>\n",
    "  **Greedy**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 2498, and profit **7098**<br>\n",
    "   **Branch-And-Bound**    \n",
    "  **Branch-And-Bound**  skipped after ```exec time 228.64s```<br>\n",
    "  **Dynamic**  ```exec time 2.67s```<br>\n",
    "     optimal weight: 2517, and profit **7117**<br>\n",
    "  **Genetic**  ```exec time 17.19s```<br>\n",
    "     optimal weight: 2495, and profit **3495**<br>\n",
    "\n",
    " --- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_1_10000_1000_1\n",
    " - capacity: *49877*<br>\n",
    " - optimal weight: *49877*, optimal profit: *563647*<br>\n",
    "  **Greedy**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 49876, and profit **563605**<br>\n",
    "  **Branch-And-Bound**  ```exec time 1.34s```<br>\n",
    "     optimal weight: 49877.0, and profit **563641.0**<br>\n",
    "  **Genetic**  ```exec time 529.28s```<br>\n",
    "     optimal weight: 23150, and profit **27414**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_2_10000_1000_1\n",
    " - capacity: *49877*<br>\n",
    " - optimal weight: *49877*, optimal profit: *90204*<br>\n",
    "  **Greedy**  ```exec time 0.02s```<br>\n",
    "     optimal weight: 49877, and profit **90200**<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.98s```<br>\n",
    "     optimal weight: 49874.0, and profit **90198.0**<br>\n",
    "  **Genetic**  ```exec time 730.94s```<br>\n",
    "     optimal weight: 30665, and profit **31779**<br>\n",
    "\n",
    "--- \n",
    "\n",
    "\n",
    "## Knapsack knapPI_3_10000_1000_1\n",
    " - capacity: *49519*<br>\n",
    " - optimal weight: *49519*, optimal profit: *146919*<br>\n",
    "  **Greedy**  ```exec time 0.04s```<br>\n",
    "     optimal weight: 49488, and profit **146888**<br>\n",
    "  **Branch-And-Bound**  ```exec time 0.85s```<br>\n",
    "     optimal weight: 49519.0, and profit **146919.0**<br>\n",
    "  **Genetic**  ```exec time 526.79s```<br>\n",
    "     optimal weight: 20570, and profit **25070**<br>\n",
    "     \n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### <center> Comparison:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|   benchmark | algorithm        |   execution mean |   execution std |   capacity |   optim_weight |   optim_profit |\n",
    "|------------:|:-----------------|-----------------:|----------------:|-----------:|---------------:|---------------:|\n",
    "|           1 | Branch-And-Bound |           0      |          0      |        165 |            165 |            309 |\n",
    "|           1 | BruteForce       |           0.0016 |          0.0005 |        165 |            165 |            309 |\n",
    "|           1 | Dynamic          |           0.006  |          0.0007 |        165 |            165 |            309 |\n",
    "|           1 | Genetic          |           0.0145 |          0.0089 |        165 |            165 |            309 |\n",
    "|           1 | Greedy           |           0      |          0      |        165 |            165 |            309 |\n",
    "|           2 | Branch-And-Bound |           0      |          0      |         26 |             26 |             51 |\n",
    "|           2 | BruteForce       |           0      |          0      |         26 |             26 |             51 |\n",
    "|           2 | Dynamic          |           0.0006 |          0.0005 |         26 |             26 |             51 |\n",
    "|           2 | Genetic          |           0.0004 |          0.0005 |         26 |             24 |             47 |\n",
    "|           2 | Greedy           |           0      |          0      |         26 |             23 |             47 |\n",
    "|           3 | Branch-And-Bound |           0.0002 |          0.0005 |        190 |            190 |            150 |\n",
    "|           3 | BruteForce       |           0      |          0      |        190 |            190 |            150 |\n",
    "|           3 | Dynamic          |           0.0044 |          0.0006 |        190 |            190 |            150 |\n",
    "|           3 | Genetic          |           0.0004 |          0.0005 |        190 |            172 |            119 |\n",
    "|           3 | Greedy           |           0      |          0      |        190 |            179 |            146 |\n",
    "|           4 | Branch-And-Bound |           0      |          0      |         50 |             50 |            107 |\n",
    "|           4 | BruteForce       |           0.0006 |          0.0005 |         50 |             50 |            107 |\n",
    "|           4 | Dynamic          |           0.0012 |          0.0004 |         50 |             50 |            107 |\n",
    "|           4 | Genetic          |           0.0014 |          0.0009 |         50 |             50 |            107 |\n",
    "|           4 | Greedy           |           0      |          0      |         50 |             48 |            102 |\n",
    "|           5 | Branch-And-Bound |           0      |          0      |        104 |            104 |            900 |\n",
    "|           5 | BruteForce       |           0.0004 |          0.0005 |        104 |            104 |            900 |\n",
    "|           5 | Dynamic          |           0.0038 |          0.0008 |        104 |            104 |            900 |\n",
    "|           5 | Genetic          |           0.0032 |          0.0008 |        104 |            103 |            898 |\n",
    "|           5 | Greedy           |           0      |          0      |        104 |             97 |            858 |\n",
    "|           6 | Branch-And-Bound |           0.0002 |          0.0004 |        170 |            169 |           1735 |\n",
    "|           6 | BruteForce       |           0.0002 |          0.0005 |        170 |            169 |           1735 |\n",
    "|           6 | Dynamic          |           0.0052 |          0.0008 |        170 |            169 |           1735 |\n",
    "|           6 | Genetic          |           0.001  |          0.0007 |        170 |            169 |           1735 |\n",
    "|           6 | Greedy           |           0      |          0      |        170 |            140 |           1478 |\n",
    "|           7 | Branch-And-Bound |           0.0042 |          0.0008 |        750 |            749 |           1458 |\n",
    "|           7 | BruteForce       |           0.0541 |          0.0147 |        750 |            749 |           1458 |\n",
    "|           7 | Dynamic          |           0.058  |          0.0047 |        750 |            749 |           1458 |\n",
    "|           7 | Genetic          |           0.306  |          0.0365 |        750 |            749 |           1458 |\n",
    "|           7 | Greedy           |           0.0002 |          0.0004 |        750 |            740 |           1441 "
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}