src/task9/task9.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "code",
   5    "execution_count": 31,
   6    "metadata": {},
   7    "outputs": [],
   8    "source": [
   9     "import itertools\n",
  10     "import collections\n",
  11     "from functools import lru_cache"
  12    ]
  13   },
  14   {
  15    "cell_type": "markdown",
  16    "metadata": {},
  17    "source": [
  18     "Needed for the recursive functions, as the `lru_cache` requires all the function's arguments be hashable. "
  19    ]
  20   },
  21   {
  22    "cell_type": "code",
  23    "execution_count": 32,
  24    "metadata": {},
  25    "outputs": [],
  26    "source": [
  27     "Element = collections.namedtuple('Element', ['weight', 'value'])"
  28    ]
  29   },
  30   {
  31    "cell_type": "code",
  32    "execution_count": 2,
  33    "metadata": {},
  34    "outputs": [],
  35    "source": [
  36     "def value_of(elements):\n",
  37     "    return sum(e['value'] for e in elements)\n",
  38     "    \n",
  39     "def weight_of(elements):\n",
  40     "    return sum(e['weight'] for e in elements)"
  41    ]
  42   },
  43   {
  44    "cell_type": "markdown",
  45    "metadata": {},
  46    "source": [
  47     "# Part 1: as many bags as possible\n",
  48     "\n",
  49     "A dynamic programming solution. See the code in part 2 (below) for an explanation: it makes more sense when we're counting the value of the bags separately from the number of bags."
  50    ]
  51   },
  52   {
  53    "cell_type": "code",
  54    "execution_count": 3,
  55    "metadata": {},
  56    "outputs": [],
  57    "source": [
  58     "def dp_count(elements, weight_limit):\n",
  59     "    count_table = {(0, j): 0 for j in range(weight_limit+1)}\n",
  60     "    back_refs = {}\n",
  61     "\n",
  62     "    for i, element in enumerate(elements):\n",
  63     "        for remaining_weight in range(weight_limit+1):\n",
  64     "            if element['weight'] > remaining_weight:\n",
  65     "                count_table[i+1, remaining_weight] = count_table[i, remaining_weight]\n",
  66     "                back_refs[i+1, remaining_weight] = (i, remaining_weight)\n",
  67     "            else:\n",
  68     "                count_table[i+1, remaining_weight] = max(\n",
  69     "                    count_table[i, remaining_weight],\n",
  70     "                    count_table[i, remaining_weight - element['weight']] + 1)\n",
  71     "                if count_table[i, remaining_weight] > count_table[i, remaining_weight - element['weight']] + 1:\n",
  72     "                    back_refs[i+1, remaining_weight] = (i, remaining_weight)\n",
  73     "                else:\n",
  74     "                    back_refs[i+1, remaining_weight] = (i, remaining_weight - element['weight'])\n",
  75     "\n",
  76     "    return count_table[len(elements), weight_limit], count_table, back_refs"
  77    ]
  78   },
  79   {
  80    "cell_type": "markdown",
  81    "metadata": {},
  82    "source": [
  83     "A recursive solution. Note the use of `lru_cache`, part of the standard `functools` Python library. The `lru_cache` memoises the function it's applied to, making these recursive algorithms feasible on larger instances."
  84    ]
  85   },
  86   {
  87    "cell_type": "code",
  88    "execution_count": 37,
  89    "metadata": {},
  90    "outputs": [],
  91    "source": [
  92     "@lru_cache(maxsize=None)\n",
  93     "def recursive_count(elements, weight_limit):\n",
  94     "    if len(elements) == 0:\n",
  95     "        return []\n",
  96     "    else:\n",
  97     "        this_element = list(elements)[0]\n",
  98     "        other_elements = elements.difference(frozenset([this_element]))\n",
  99     "        if this_element.weight > weight_limit:\n",
 100     "            return recursive_count(other_elements, weight_limit)\n",
 101     "        else:\n",
 102     "            with_this = recursive_count(other_elements, weight_limit - this_element.weight)\n",
 103     "            without_this = recursive_count(other_elements, weight_limit)\n",
 104     "            if len(with_this) + 1 > len(without_this):\n",
 105     "                return [this_element] + with_this\n",
 106     "            else:\n",
 107     "                return without_this"
 108    ]
 109   },
 110   {
 111    "cell_type": "markdown",
 112    "metadata": {},
 113    "source": [
 114     "Finally, a greedy version that just packs the lightest bags in first, continuing while there's space for another."
 115    ]
 116   },
 117   {
 118    "cell_type": "code",
 119    "execution_count": 10,
 120    "metadata": {},
 121    "outputs": [],
 122    "source": [
 123     "def greedy_fill(elements, weight_limit):\n",
 124     "    return len(list(itertools.takewhile(lambda s: s < weight_limit, itertools.accumulate(sorted(e['weight'] for e in elements)))))"
 125    ]
 126   },
 127   {
 128    "cell_type": "markdown",
 129    "metadata": {},
 130    "source": [
 131     "# Part 2: getting the most value\n",
 132     "First, the dynamic programming solution.\n",
 133     "\n",
 134     "The table is indexed as `(number of bags, weight used)` and contains the solution (i.e. value of the chosen bags) for the problem when using the first few bags and a smaller weight limit. When considering adding this bag, look at the solutions for whether to use this bag or not.\n",
 135     "\n",
 136     "Let's say we're looking at including bag _i_ and a total weight limit of _wl_. \n",
 137     "* If we're not using this bag, the best solution is given by the best solution for the _i_-1 other bags with the same weight limit _wl_. \n",
 138     "* If we _are_ using this bag, the best solution is the value of this bag plus the best solution for the other _i_-1 bags packed into (_wl_ - this bag's weight). We need the smaller weight limit to ensure there's enough space to fit this bag.\n",
 139     "\n",
 140     "We can fill the table row by row, looking up the values in the row above. \n",
 141     "\n",
 142     "The final solution is read off from the table, in the cell that represents all the bags and the full weight limit.\n",
 143     "\n",
 144     "The backpointers are there to easily trace back which decision was made when filling in each cell. That allows you to reconstruct the full solution."
 145    ]
 146   },
 147   {
 148    "cell_type": "code",
 149    "execution_count": 5,
 150    "metadata": {},
 151    "outputs": [],
 152    "source": [
 153     "def dp_value(elements, weight_limit):\n",
 154     "    value_table = {(0, j): 0 for j in range(weight_limit+1)}\n",
 155     "    back_refs = {}\n",
 156     "    \n",
 157     "    for i, element in enumerate(elements):\n",
 158     "        for wl in range(weight_limit+1):\n",
 159     "            if element['weight'] > wl:\n",
 160     "                value_table[i+1, wl] = value_table[i, wl]\n",
 161     "                back_refs[i+1, wl] = (i, wl)\n",
 162     "\n",
 163     "            else:\n",
 164     "                value_table[i+1, wl] = max(\n",
 165     "                    value_table[i, wl],\n",
 166     "                    value_table[i, wl - element['weight']] + element['value'])\n",
 167     "                if value_table[i, wl] > value_table[i, wl - element['weight']] + element['value']:\n",
 168     "                    back_refs[i+1, wl] = (i, wl)\n",
 169     "                else:\n",
 170     "                    back_refs[i+1, wl] = (i, wl - element['weight'])\n",
 171     "\n",
 172     "    return value_table[len(elements), weight_limit], value_table, back_refs"
 173    ]
 174   },
 175   {
 176    "cell_type": "markdown",
 177    "metadata": {},
 178    "source": [
 179     "A recursive definition, directly applying the ideas above. Without memoisation, this just won't terminate on even trivial-sized problems. "
 180    ]
 181   },
 182   {
 183    "cell_type": "code",
 184    "execution_count": 58,
 185    "metadata": {},
 186    "outputs": [],
 187    "source": [
 188     "@lru_cache(maxsize=None)\n",
 189     "def recursive_value(elements, weight_limit):\n",
 190     "    if len(elements) == 0:\n",
 191     "        return frozenset()\n",
 192     "    else:\n",
 193     "        this_element = next(iter(elements)) # pick an arbitrary element\n",
 194     "        other_elements = elements.difference(frozenset([this_element]))\n",
 195     "        if this_element.weight > weight_limit:\n",
 196     "            return recursive_value(other_elements, weight_limit)\n",
 197     "        else:\n",
 198     "            with_this = recursive_value(other_elements, weight_limit - this_element.weight)\n",
 199     "            without_this = recursive_value(other_elements, weight_limit)\n",
 200     "            items_with_this = with_this.union(frozenset([this_element]))\n",
 201     "            if sum(e.value for e in items_with_this) > sum(e.value for e in without_this):\n",
 202     "                return items_with_this\n",
 203     "            else:\n",
 204     "                return without_this"
 205    ]
 206   },
 207   {
 208    "cell_type": "markdown",
 209    "metadata": {},
 210    "source": [
 211     "A couple of greedy attempts. The first tries to pack the items by weight, always putting in the lightest items first.\n",
 212     "\n",
 213     "The second tries to be a bit more clever and sorts the items by pennies-per-kilo, so the highest-value bags are placed first."
 214    ]
 215   },
 216   {
 217    "cell_type": "code",
 218    "execution_count": 12,
 219    "metadata": {},
 220    "outputs": [],
 221    "source": [
 222     "def greedy_value_w(elements, weight_limit):\n",
 223     "    return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
 224     "                     itertools.accumulate(\n",
 225     "                         sorted((e for e in elements), key=lambda e: e['weight']),\n",
 226     "                         lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
 227     "               )[-1]['value']"
 228    ]
 229   },
 230   {
 231    "cell_type": "code",
 232    "execution_count": 11,
 233    "metadata": {},
 234    "outputs": [],
 235    "source": [
 236     "def greedy_value_vpw(elements, weight_limit):\n",
 237     "    return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
 238     "                     itertools.accumulate(\n",
 239     "                         sorted((e for e in elements), key=lambda e: e['value'] / e['weight'], reverse=True),\n",
 240     "                         lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
 241     "               )[-1]['value']"
 242    ]
 243   },
 244   {
 245    "cell_type": "markdown",
 246    "metadata": {},
 247    "source": [
 248     "# Utilities\n",
 249     "A couple of functions for displaying the results. Only try these on the small example in the question, as otherwise there won't be enough screen area to display the table!"
 250    ]
 251   },
 252   {
 253    "cell_type": "code",
 254    "execution_count": 7,
 255    "metadata": {},
 256    "outputs": [],
 257    "source": [
 258     "def display_table(table, suppress_zero=True):\n",
 259     "    def formatted_row_element(e, suppress_zero):\n",
 260     "        if suppress_zero and e == 0:\n",
 261     "            return '   .'\n",
 262     "        else:\n",
 263     "            return '{:4d}'.format(e)\n",
 264     "    \n",
 265     "    \n",
 266     "    rows = max(k[0] for k in table.keys())\n",
 267     "    columns = max(k[1] for k in table.keys())\n",
 268     "    for r in range(rows+1):\n",
 269     "#         print(''.join('{:4d} '.format(table[r, c]) for c in range(columns + 1)))\n",
 270     "        print(' '.join(formatted_row_element(table[r, c], suppress_zero) for c in range(columns + 1)))"
 271    ]
 272   },
 273   {
 274    "cell_type": "code",
 275    "execution_count": 8,
 276    "metadata": {},
 277    "outputs": [],
 278    "source": [
 279     "def backtrace(table):\n",
 280     "    r = max(k[0] for k in table.keys())\n",
 281     "    c = max(k[1] for k in table.keys())\n",
 282     "    back_table = {}\n",
 283     "    while r > 0:\n",
 284     "        back_table[r, c] = table[r, c]\n",
 285     "        r, c = table[r, c]\n",
 286     "    return back_table"
 287    ]
 288   },
 289   {
 290    "cell_type": "code",
 291    "execution_count": 9,
 292    "metadata": {},
 293    "outputs": [],
 294    "source": [
 295     "def traced_table(base, backtrace):\n",
 296     "    return {k: base[k] if k in backtrace else 0 for k in base}"
 297    ]
 298   },
 299   {
 300    "cell_type": "markdown",
 301    "metadata": {},
 302    "source": [
 303     "# Solving the problems\n",
 304     "Finally, how to solve the problem!\n",
 305     "\n",
 306     "Load the elements, convert them into something hashable for the recursive solutions."
 307    ]
 308   },
 309   {
 310    "cell_type": "code",
 311    "execution_count": 13,
 312    "metadata": {},
 313    "outputs": [],
 314    "source": [
 315     "elements = [{'weight': int(l.strip().split()[0]), 'value': int(l.strip().split()[1])} \n",
 316     "            for l in open('../../data/09-bags.txt')]\n",
 317     "weight_limit = 5000"
 318    ]
 319   },
 320   {
 321    "cell_type": "code",
 322    "execution_count": 33,
 323    "metadata": {},
 324    "outputs": [],
 325    "source": [
 326     "hashable_elements = frozenset(\n",
 327     "    Element(weight=e['weight'], value=e['value']) for e in elements\n",
 328     "    )"
 329    ]
 330   },
 331   {
 332    "cell_type": "markdown",
 333    "metadata": {},
 334    "source": [
 335     "## Solving part 1\n",
 336     "\n",
 337     "All the approaches find the optimal solution."
 338    ]
 339   },
 340   {
 341    "cell_type": "code",
 342    "execution_count": 14,
 343    "metadata": {},
 344    "outputs": [
 345     {
 346      "data": {
 347       "text/plain": [
 348        "15"
 349       ]
 350      },
 351      "execution_count": 14,
 352      "metadata": {},
 353      "output_type": "execute_result"
 354     }
 355    ],
 356    "source": [
 357     "value, ct, br  = dp_count(elements, weight_limit)\n",
 358     "value"
 359    ]
 360   },
 361   {
 362    "cell_type": "code",
 363    "execution_count": 15,
 364    "metadata": {},
 365    "outputs": [
 366     {
 367      "data": {
 368       "text/plain": [
 369        "15"
 370       ]
 371      },
 372      "execution_count": 15,
 373      "metadata": {},
 374      "output_type": "execute_result"
 375     }
 376    ],
 377    "source": [
 378     "greedy_fill(elements, weight_limit)"
 379    ]
 380   },
 381   {
 382    "cell_type": "code",
 383    "execution_count": 39,
 384    "metadata": {},
 385    "outputs": [
 386     {
 387      "data": {
 388       "text/plain": [
 389        "15"
 390       ]
 391      },
 392      "execution_count": 39,
 393      "metadata": {},
 394      "output_type": "execute_result"
 395     }
 396    ],
 397    "source": [
 398     "len(recursive_count(hashable_elements, weight_limit))"
 399    ]
 400   },
 401   {
 402    "cell_type": "markdown",
 403    "metadata": {},
 404    "source": [
 405     "## Solving part 2\n",
 406     "\n",
 407     "The dynamic programming version find the optimal solution."
 408    ]
 409   },
 410   {
 411    "cell_type": "code",
 412    "execution_count": 66,
 413    "metadata": {},
 414    "outputs": [
 415     {
 416      "data": {
 417       "text/plain": [
 418        "2383"
 419       ]
 420      },
 421      "execution_count": 66,
 422      "metadata": {},
 423      "output_type": "execute_result"
 424     }
 425    ],
 426    "source": [
 427     "value, vt, vbr = dp_value(elements, weight_limit)\n",
 428     "value"
 429    ]
 430   },
 431   {
 432    "cell_type": "markdown",
 433    "metadata": {},
 434    "source": [
 435     "The greedy versions don't find optimal solutions, but the smarter algorithm gets pretty close."
 436    ]
 437   },
 438   {
 439    "cell_type": "code",
 440    "execution_count": 17,
 441    "metadata": {},
 442    "outputs": [
 443     {
 444      "data": {
 445       "text/plain": [
 446        "1801"
 447       ]
 448      },
 449      "execution_count": 17,
 450      "metadata": {},
 451      "output_type": "execute_result"
 452     }
 453    ],
 454    "source": [
 455     "greedy_value_w(elements, weight_limit)"
 456    ]
 457   },
 458   {
 459    "cell_type": "code",
 460    "execution_count": 18,
 461    "metadata": {},
 462    "outputs": [
 463     {
 464      "data": {
 465       "text/plain": [
 466        "2300"
 467       ]
 468      },
 469      "execution_count": 18,
 470      "metadata": {},
 471      "output_type": "execute_result"
 472     }
 473    ],
 474    "source": [
 475     "greedy_value_vpw(elements, weight_limit)"
 476    ]
 477   },
 478   {
 479    "cell_type": "markdown",
 480    "metadata": {},
 481    "source": [
 482     "The recursive solution also finds the optimal solution,but only thanks to memoisation."
 483    ]
 484   },
 485   {
 486    "cell_type": "code",
 487    "execution_count": 69,
 488    "metadata": {},
 489    "outputs": [
 490     {
 491      "data": {
 492       "text/plain": [
 493        "frozenset({Element(weight=301, value=134),\n",
 494        "           Element(weight=314, value=166),\n",
 495        "           Element(weight=320, value=154),\n",
 496        "           Element(weight=336, value=190),\n",
 497        "           Element(weight=337, value=140),\n",
 498        "           Element(weight=340, value=172),\n",
 499        "           Element(weight=353, value=191),\n",
 500        "           Element(weight=356, value=153),\n",
 501        "           Element(weight=359, value=171),\n",
 502        "           Element(weight=365, value=177),\n",
 503        "           Element(weight=381, value=166),\n",
 504        "           Element(weight=382, value=185),\n",
 505        "           Element(weight=414, value=189),\n",
 506        "           Element(weight=434, value=195)})"
 507       ]
 508      },
 509      "execution_count": 69,
 510      "metadata": {},
 511      "output_type": "execute_result"
 512     }
 513    ],
 514    "source": [
 515     "recursive_items = recursive_value(hashable_elements, weight_limit)\n",
 516     "recursive_items"
 517    ]
 518   },
 519   {
 520    "cell_type": "code",
 521    "execution_count": 70,
 522    "metadata": {},
 523    "outputs": [
 524     {
 525      "data": {
 526       "text/plain": [
 527        "2383"
 528       ]
 529      },
 530      "execution_count": 70,
 531      "metadata": {},
 532      "output_type": "execute_result"
 533     }
 534    ],
 535    "source": [
 536     "sum(e.value for e in recursive_items)"
 537    ]
 538   },
 539   {
 540    "cell_type": "markdown",
 541    "metadata": {},
 542    "source": [
 543     "Let's check that these two solutions include the same elements. Use the `backtrace` function to find when new items were added to the optimal order."
 544    ]
 545   },
 546   {
 547    "cell_type": "code",
 548    "execution_count": 78,
 549    "metadata": {},
 550    "outputs": [
 551     {
 552      "data": {
 553       "text/plain": [
 554        "[Element(weight=301, value=134),\n",
 555        " Element(weight=314, value=166),\n",
 556        " Element(weight=320, value=154),\n",
 557        " Element(weight=336, value=190),\n",
 558        " Element(weight=337, value=140),\n",
 559        " Element(weight=340, value=172),\n",
 560        " Element(weight=353, value=191),\n",
 561        " Element(weight=356, value=153),\n",
 562        " Element(weight=359, value=171),\n",
 563        " Element(weight=365, value=177),\n",
 564        " Element(weight=381, value=166),\n",
 565        " Element(weight=382, value=185),\n",
 566        " Element(weight=414, value=189),\n",
 567        " Element(weight=434, value=195)]"
 568       ]
 569      },
 570      "execution_count": 78,
 571      "metadata": {},
 572      "output_type": "execute_result"
 573     }
 574    ],
 575    "source": [
 576     "dp_items = [element for (pre, post), element in zip(backtrace(vbr).items(), reversed(elements))\n",
 577     "             if pre[1] != post[1] ]\n",
 578     "dp_items_fs = frozenset(\n",
 579     "    Element(weight=e['weight'], value=e['value']) for e in dp_items\n",
 580     "    )\n",
 581     "sorted(dp_items_fs)"
 582    ]
 583   },
 584   {
 585    "cell_type": "code",
 586    "execution_count": 79,
 587    "metadata": {},
 588    "outputs": [
 589     {
 590      "data": {
 591       "text/plain": [
 592        "True"
 593       ]
 594      },
 595      "execution_count": 79,
 596      "metadata": {},
 597      "output_type": "execute_result"
 598     }
 599    ],
 600    "source": [
 601     "dp_items_fs == recursive_items"
 602    ]
 603   },
 604   {
 605    "cell_type": "code",
 606    "execution_count": null,
 607    "metadata": {},
 608    "outputs": [],
 609    "source": []
 610   }
 611  ],
 612  "metadata": {
 613   "kernelspec": {
 614    "display_name": "Python 3",
 615    "language": "python",
 616    "name": "python3"
 617   },
 618   "language_info": {
 619    "codemirror_mode": {
 620     "name": "ipython",
 621     "version": 3
 622    },
 623    "file_extension": ".py",
 624    "mimetype": "text/x-python",
 625    "name": "python",
 626    "nbconvert_exporter": "python",
 627    "pygments_lexer": "ipython3",
 628    "version": "3.6.6"
 629   }
 630  },
 631  "nbformat": 4,
 632  "nbformat_minor": 2
 633 }