{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "19a17ff2", "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "def random_request():\n", " return [sorted(random.sample(range(100),2)), random.random()*10]" ] }, { "cell_type": "code", "execution_count": 3, "id": "1fbba6d3", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[38, 54], 4.1886485190133635]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "random_request()" ] }, { "cell_type": "code", "execution_count": 4, "id": "ecd4b9ce", "metadata": {}, "outputs": [], "source": [ "def make_requests(n):\n", " return [random_request() for i in range(n)]" ] }, { "cell_type": "code", "execution_count": 5, "id": "f66f612c", "metadata": {}, "outputs": [], "source": [ "def compatible(r1, r2):\n", " return r2[0][1] <= r1[0][0] or r2[0][0] >= r1[0][1]\n", "\n", "def is_compatible(request, solution):\n", " return all(compatible(request, r) for r in solution)" ] }, { "cell_type": "code", "execution_count": 24, "id": "5d12ad6e", "metadata": {}, "outputs": [], "source": [ "def plot_requests(requests):\n", " for r in sorted(requests, key=lambda x : x[0][1]):\n", " print(\" \"*(r[0][0]) + \"-\"*(r[0][1]-r[0][0]) + \" (\" + str(round(r[1],2)) + \")\")\n", " #print(\"total value:\",sum(r[1] for r in requests))\n", " total_value = sum(r[1] for r in requests)\n", " print(f\"total value: {total_value}\")" ] }, { "cell_type": "code", "execution_count": 7, "id": "8af41160", "metadata": {}, "outputs": [], "source": [ "# best = most valuable\n", "def greedy(requests):\n", " sorted_requests = sorted(requests, key=lambda r: r[1], reverse=True)\n", " solution = []\n", " solution.append(sorted_requests.pop(0))\n", " \n", " while len(sorted_requests) > 0:\n", " request = sorted_requests.pop(0)\n", " if is_compatible(request, solution):\n", " solution.append(request)\n", " \n", " return solution" ] }, { "cell_type": "code", "execution_count": 8, "id": "33eda987", "metadata": {}, "outputs": [], "source": [ "requests = make_requests(100)" ] }, { "cell_type": "code", "execution_count": 9, "id": "751e8677", "metadata": {}, "outputs": [], "source": [ "sol = greedy(requests)" ] }, { "cell_type": "code", "execution_count": 10, "id": "8c4c02b8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " - (7.06)\n", " -- (2.8)\n", "---------------- (5.05)\n", " ------------- (7.64)\n", " ---------------- (2.12)\n", " ---------- (6.73)\n", " -------------------- (6.56)\n", " ------------ (5.47)\n", " ------------ (1.36)\n", " ---------------------- (1.19)\n", " ------------------------------------ (6.97)\n", " ----------------- (1.85)\n", " --------------------------------------------- (2.55)\n", " ----------------------------------------- (2.07)\n", " --------------------------------------- (9.56)\n", " -------- (9.05)\n", " ---- (9.34)\n", " ---------------------------------- (9.24)\n", " ----------------------------------------- (5.96)\n", " - (5.45)\n", " ------------ (5.81)\n", "------------------------------------------------------- (3.42)\n", " ------------------------------------------------ (4.93)\n", " ------------------- (9.43)\n", " -- (7.44)\n", " ------------------ (6.06)\n", " ------------------------------------------------------- (7.28)\n", " ---------------- (9.83)\n", " ----------------------------------- (9.8)\n", " ------------ (0.43)\n", " ------------------------------------------ (9.31)\n", " ----------------------------------------------------- (5.9)\n", " -------------------------------------------------- (7.07)\n", " ---------------- (1.77)\n", " ----- (7.87)\n", " ------------------ (1.5)\n", " ---------------------------------------- (5.51)\n", " ------------- (8.28)\n", " -------------- (8.65)\n", " --------------------------------------------------- (7.6)\n", " ---------------------------------------------------------- (6.48)\n", " ---------------------------------------- (8.43)\n", " ----------------------------------- (6.17)\n", " ------------------------------------------------ (7.92)\n", " ----------------------- (2.25)\n", " ------------------------------------------------------------ (9.8)\n", " ------------------------------------------------------------------ (3.88)\n", " ------------------------------------ (7.4)\n", " --------------------------------------------- (3.64)\n", " ----- (0.67)\n", " --------------- (5.31)\n", " -- (3.9)\n", " ------------------------------------- (6.53)\n", " ----------------------------------------------- (5.47)\n", " - (7.5)\n", " ------------------- (3.68)\n", " -------------------------------------- (4.04)\n", " ------------------------------------------- (3.77)\n", " ---------------------------------------------------------- (8.02)\n", " ---------------------------------------------- (8.58)\n", " ----- (2.23)\n", " ------------------------ (9.4)\n", " -------------------------------------------------------------- (3.46)\n", " ------------ (6.19)\n", " ------------------------------------------------------------------------------------ (7.32)\n", " ---------------------------------------------------------------------- (8.14)\n", " ----------------------------------------------------- (6.5)\n", " ------------------------------------------------------------------------- (4.44)\n", " ---------------------------------------------------------------------------------- (0.63)\n", " ----------------------------------- (8.12)\n", " ------------------------------------------------------------------------ (1.66)\n", " -------------------------------------------------------------------------------- (3.67)\n", " ------------------------------------ (2.45)\n", " ---------------------------------------------------------------------------------- (3.64)\n", " ------------------------------------------------------ (2.34)\n", " ---- (6.18)\n", " ----------------------------------------------------------- (3.3)\n", " ---------------------------------------------------------- (5.58)\n", " ------------------------------------------------------------------ (6.84)\n", " ----------------------------------------- (4.39)\n", " -- (1.03)\n", " ------ (0.52)\n", " ---------------------------- (3.55)\n", " ------------------------------- (4.96)\n", " ---------------------- (0.35)\n", " ------------------------------------------- (5.2)\n", " ----------------------------------------------------------------------------- (6.05)\n", " --------------- (9.04)\n", " ----------------------------------------------------------------------------------- (1.13)\n", " --------- (9.95)\n", " ------------------------------------------------------------------ (7.44)\n", " -------------------------------------- (4.99)\n", " ---------- (6.91)\n", " ---------------------------------------------------- (7.32)\n", " ------------------------------------------------------ (4.82)\n", " ------------------------------------------ (1.35)\n", " -------------------------------------------------- (2.16)\n", " ---------------------------- (0.16)\n", " ---------------------------------- (9.16)\n", " -------- (7.53)\n" ] } ], "source": [ "plot_requests(requests)" ] }, { "cell_type": "code", "execution_count": 11, "id": "6444c6f2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " ------------- (7.64)\n", " ---------- (6.73)\n", " ---------------- (9.83)\n", " ----- (7.87)\n", " -- (3.9)\n", " - (7.5)\n", " ----- (2.23)\n", " --------- (9.95)\n" ] } ], "source": [ "plot_requests(sol)" ] }, { "cell_type": "code", "execution_count": 13, "id": "19e78f75", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "55.64068759685977" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sum(s[1] for s in sol)" ] }, { "cell_type": "code", "execution_count": 14, "id": "94b24582", "metadata": {}, "outputs": [], "source": [ "# best = most valuable\n", "# best = shortest\n", "# best = most value-dense (highest value/duration)" ] }, { "cell_type": "code", "execution_count": 15, "id": "7da69936", "metadata": {}, "outputs": [], "source": [ "def greedy(requests, sort_function):\n", " sorted_requests = sorted(requests, key=sort_function)\n", " solution = []\n", " solution.append(sorted_requests.pop(0))\n", " \n", " while len(sorted_requests) > 0:\n", " request = sorted_requests.pop(0)\n", " if is_compatible(request, solution):\n", " solution.append(request)\n", " \n", " return solution" ] }, { "cell_type": "code", "execution_count": 23, "id": "963f2d3d", "metadata": {}, "outputs": [], "source": [ "# request = [[start, end], value]\n", "most_value = lambda req : -req[1]\n", "shortest = lambda req : req[0][1] - req[0][0]\n", "density = lambda req : -req[1]/(req[0][1] - req[0][0])" ] }, { "cell_type": "code", "execution_count": 17, "id": "5f48de7b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " at 0x1044bf4c0>\n" ] } ], "source": [ "print(most_value)" ] }, { "cell_type": "code", "execution_count": 30, "id": "931925d1", "metadata": {}, "outputs": [], "source": [ "requests = make_requests(1000)" ] }, { "cell_type": "code", "execution_count": 31, "id": "87a2164d", "metadata": {}, "outputs": [], "source": [ "s1 = greedy(requests, most_value)\n", "s2 = greedy(requests, shortest)\n", "s3 = greedy(requests, density)" ] }, { "cell_type": "code", "execution_count": 32, "id": "2546b18d", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " -- (8.41)\n", " -- (7.99)\n", " - (9.88)\n", " - (3.24)\n", " - (7.75)\n", " - (4.72)\n", " ---- (8.9)\n", " ------------------------------------------ (10.0)\n", " ---- (1.84)\n", " - (6.33)\n", " -- (9.82)\n", " --- (3.63)\n", " --- (9.54)\n", " - (9.65)\n", " -------------------- (9.98)\n", "total value: 111.67204639509534\n" ] } ], "source": [ "plot_requests(s1)" ] }, { "cell_type": "code", "execution_count": 33, "id": "bdcd7c17", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " -- (8.41)\n", " - (2.89)\n", " - (9.88)\n", " - (3.24)\n", " - (7.75)\n", " - (4.72)\n", " -- (1.68)\n", " - (6.77)\n", " - (0.3)\n", " - (6.84)\n", " -- (8.33)\n", " -- (4.39)\n", " -- (6.73)\n", " ----- (9.13)\n", " - (8.56)\n", " - (9.34)\n", " - (4.27)\n", " -- (9.23)\n", " -- (7.14)\n", " - (8.35)\n", " - (4.04)\n", " - (1.87)\n", " - (4.08)\n", " ---- (1.84)\n", " - (6.33)\n", " -- (9.82)\n", " - (1.26)\n", " - (6.97)\n", " - (5.18)\n", " - (9.65)\n", " - (2.99)\n", " -- (9.72)\n", " - (4.32)\n", " -- (2.83)\n", " - (2.17)\n", " -- (0.51)\n", " - (6.08)\n", " - (7.57)\n", "total value: 215.16286366215562\n" ] } ], "source": [ "plot_requests(s2)" ] }, { "cell_type": "code", "execution_count": 34, "id": "61d612ec", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " -- (8.41)\n", " -- (7.99)\n", " - (9.88)\n", " - (3.24)\n", " - (7.75)\n", " - (4.72)\n", " ---- (8.9)\n", " - (6.77)\n", " - (0.3)\n", " - (6.84)\n", " -- (8.33)\n", " -- (4.39)\n", " -- (6.73)\n", " ----- (9.13)\n", " - (8.56)\n", " - (9.34)\n", " - (4.27)\n", " -- (9.23)\n", " -- (7.14)\n", " - (8.35)\n", " - (4.04)\n", " - (1.87)\n", " - (4.08)\n", " ---- (1.84)\n", " - (6.33)\n", " -- (9.82)\n", " - (1.26)\n", " - (6.97)\n", " - (5.18)\n", " - (9.65)\n", " - (2.99)\n", " -- (9.72)\n", " - (4.32)\n", " -- (2.83)\n", " - (2.17)\n", " ----- (7.32)\n", " - (6.08)\n", " - (7.57)\n", "total value: 234.29789829029843\n" ] } ], "source": [ "plot_requests(s3)" ] }, { "cell_type": "code", "execution_count": null, "id": "0b3b27fd", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "2e45b0cd", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.10" } }, "nbformat": 4, "nbformat_minor": 5 }