interview.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the described problem is a classical modification of the binpacking problem know from literature\n",
    "# they can be solved simply by evaluating combinations, specific optimized algorithms for bin packing or optimization solvers\n",
    "# below I show how to quickly find the maximum number of packages fitting (max_length) in dependence of the weight constraint\n",
    "# at the end I also demonstrate how to use a solver to achive the same thing "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "weights = [8.08, 5.7, 7.8, 3.2, 2.1, 11, 4.44, 6.4, 16.3, 1.7]\n",
    "prices = [24, 28.3, 210, 10.2, 4.4, 40.5, 17, 35.6, 82.7, 14.6]\n",
    "\n",
    "max_weight = 50"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "921"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "import itertools\n",
    "\n",
    "# to get all the combinations we can just iterate through all the combinations and check if the sum of their weight would fit the basket\n",
    "\n",
    "combinations = []\n",
    "for i in range(len(weights)):\n",
    "    for combo in itertools.combinations(weights, i + 1):\n",
    "        if sum(combo) <= max_weight:\n",
    "            combinations.append(combo)\n",
    "\n",
    "len(combinations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_length = max(map(len, combinations))\n",
    "max_length  # this gives the maximum number of packages that we can make fit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "combinations_min_price = []\n",
    "combination_prices = []\n",
    "for combo in itertools.combinations(zip(weights, prices), max_length):\n",
    "    combo_weights = [c[0] for c in combo]\n",
    "    combo_prices = [c[1] for c in combo]\n",
    "    if sum(combo_weights) <= max_weight:\n",
    "        combinations_min_price.append(combo_weights)\n",
    "        combination_prices.append(sum(combo_prices))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "indices = []\n",
    "\n",
    "for element in combinations_min_price[combination_prices.index(min(combination_prices))]:\n",
    "    index = weights.index(element)\n",
    "    indices.append(index + 1)   # since in the pptx it starts with 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This are the packages to choose to get the max number of packages possible with the lowest possible price [1, 2, 4, 5, 6, 7, 8, 10]  price  174.6\n"
     ]
    }
   ],
   "source": [
    "print(\"This are the packages to choose to get the max number of packages possible with the lowest possible price\", indices, \" price \", min(combination_prices))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_weight = 35     # same thing reducing the weight, not sure if the number \"2\" is part of the question, bc. there are still a max of 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "563"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "combinations_min_price = []\n",
    "combination_prices = []\n",
    "\n",
    "for i in range(len(weights)):\n",
    "    for combo in itertools.combinations(zip(weights, prices), i + 1):\n",
    "        combo_weights = [c[0] for c in combo]\n",
    "        combo_prices = [c[1] for c in combo]\n",
    "        if sum(combo_weights) <= max_weight:\n",
    "            combinations_min_price.append(combo_weights)\n",
    "            combination_prices.append(sum(combo_prices))\n",
    "len(combinations_min_price)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max_length = max(map(len, combinations_min_price))\n",
    "max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "combinations_min_price = []\n",
    "combination_prices = []\n",
    "for combo in itertools.combinations(zip(weights, prices), max_length):\n",
    "    combo_weights = [c[0] for c in combo]\n",
    "    combo_prices = [c[1] for c in combo]\n",
    "    if sum(combo_weights) <= max_weight:\n",
    "        combinations_min_price.append(combo_weights)\n",
    "        combination_prices.append(sum(combo_prices))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "indices = []\n",
    "\n",
    "for element in combinations_min_price[combination_prices.index(min(combination_prices))]:\n",
    "    index = weights.index(element)\n",
    "    indices.append(index + 1)   # since in the pptx it starts with 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This are the packages to choose to get the max number of packages possible with the lowest possible price [1, 2, 4, 5, 7, 8, 10]  price  134.1\n"
     ]
    }
   ],
   "source": [
    "print(\"This are the packages to choose to get the max number of packages possible with the lowest possible price\", indices, \" price \", min(combination_prices))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimal\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Optimal'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# you can get the same result using a lin-op solver but in this case you have to weight the objectives\n",
    "\n",
    "from pulp import LpVariable, LpProblem, LpMinimize, LpStatus, value\n",
    "\n",
    "n = len(weights)\n",
    "\n",
    "x = [LpVariable(f\"x{i}\", 0, 1, \"Integer\") for i in range(n)]\n",
    "\n",
    "prob = LpProblem(\"binpacking\", LpMinimize)\n",
    "prob += sum([x[i] * prices[i]  for i in range(n)]) - (1000 * sum([x[i] for i in range(n)]))\n",
    "\n",
    "prob += sum([x[i] * weights[i] for i in range(n)]) <= max_weight\n",
    "\n",
    "\n",
    "status = prob.solve()\n",
    "\n",
    "print(LpStatus[status])\n",
    "\n",
    "LpStatus[status]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1.0, 1.0, 0.0, 1.0, 1.0, 0.0, 1.0, 1.0, 0.0, 1.0]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[value(v) for v in x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "venv",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "448c910ad216f01234801873adc95a0014e09ac8a0901dce036318363fa9d70c"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}