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": "code",
  16    "execution_count": 2,
  17    "metadata": {},
  18    "outputs": [],
  19    "source": [
  20     "def value_of(elements):\n",
  21     "    return sum(e['value'] for e in elements)\n",
  22     "    \n",
  23     "def weight_of(elements):\n",
  24     "    return sum(e['weight'] for e in elements)"
  25    ]
  26   },
  27   {
  28    "cell_type": "code",
  29    "execution_count": 32,
  30    "metadata": {},
  31    "outputs": [],
  32    "source": [
  33     "Element = collections.namedtuple('Element', ['weight', 'value'])"
  34    ]
  35   },
  36   {
  37    "cell_type": "code",
  38    "execution_count": 3,
  39    "metadata": {},
  40    "outputs": [],
  41    "source": [
  42     "def dp_count(elements, weight_limit):\n",
  43     "    count_table = {(0, j): 0 for j in range(weight_limit+1)}\n",
  44     "    back_refs = {}\n",
  45     "\n",
  46     "    for i, element in enumerate(elements):\n",
  47     "        for remaining_weight in range(weight_limit+1):\n",
  48     "            if element['weight'] > remaining_weight:\n",
  49     "                count_table[i+1, remaining_weight] = count_table[i, remaining_weight]\n",
  50     "                back_refs[i+1, remaining_weight] = (i, remaining_weight)\n",
  51     "            else:\n",
  52     "                count_table[i+1, remaining_weight] = max(\n",
  53     "                    count_table[i, remaining_weight],\n",
  54     "                    count_table[i, remaining_weight - element['weight']] + 1)\n",
  55     "                if count_table[i, remaining_weight] > count_table[i, remaining_weight - element['weight']] + 1:\n",
  56     "                    back_refs[i+1, remaining_weight] = (i, remaining_weight)\n",
  57     "                else:\n",
  58     "                    back_refs[i+1, remaining_weight] = (i, remaining_weight - element['weight'])\n",
  59     "\n",
  60     "    return count_table[len(elements), weight_limit], count_table, back_refs"
  61    ]
  62   },
  63   {
  64    "cell_type": "code",
  65    "execution_count": 37,
  66    "metadata": {},
  67    "outputs": [],
  68    "source": [
  69     "@lru_cache(maxsize=None)\n",
  70     "def recursive_count(elements, weight_limit):\n",
  71     "    if len(elements) == 0:\n",
  72     "        return []\n",
  73     "    else:\n",
  74     "        this_element = list(elements)[0]\n",
  75     "        other_elements = elements.difference(frozenset([this_element]))\n",
  76     "#         this_element = elements[0]\n",
  77     "#         other_elements = elements[1:]\n",
  78     "        if this_element.weight > weight_limit:\n",
  79     "            return recursive_count(other_elements, weight_limit)\n",
  80     "        else:\n",
  81     "            with_this = recursive_count(other_elements, weight_limit - this_element.weight)\n",
  82     "            without_this = recursive_count(other_elements, weight_limit)\n",
  83     "            if len(with_this) + 1 > len(without_this):\n",
  84     "                return [this_element] + with_this\n",
  85     "            else:\n",
  86     "                return without_this"
  87    ]
  88   },
  89   {
  90    "cell_type": "code",
  91    "execution_count": 5,
  92    "metadata": {},
  93    "outputs": [],
  94    "source": [
  95     "def dp_value(elements, weight_limit):\n",
  96     "    value_table = {(0, j): 0 for j in range(weight_limit+1)}\n",
  97     "    back_refs = {}\n",
  98     "    \n",
  99     "    for i, element in enumerate(elements):\n",
 100     "        for wl in range(weight_limit+1):\n",
 101     "            if element['weight'] > wl:\n",
 102     "                value_table[i+1, wl] = value_table[i, wl]\n",
 103     "                back_refs[i+1, wl] = (i, wl)\n",
 104     "\n",
 105     "            else:\n",
 106     "                value_table[i+1, wl] = max(\n",
 107     "                    value_table[i, wl],\n",
 108     "                    value_table[i, wl - element['weight']] + element['value'])\n",
 109     "                if value_table[i, wl] > value_table[i, wl - element['weight']] + element['value']:\n",
 110     "                    back_refs[i+1, wl] = (i, wl)\n",
 111     "                else:\n",
 112     "                    back_refs[i+1, wl] = (i, wl - element['weight'])\n",
 113     "\n",
 114     "    return value_table[len(elements), weight_limit], value_table, back_refs"
 115    ]
 116   },
 117   {
 118    "cell_type": "code",
 119    "execution_count": 19,
 120    "metadata": {},
 121    "outputs": [
 122     {
 123      "data": {
 124       "text/plain": [
 125        "frozenset({1, 2, 3})"
 126       ]
 127      },
 128      "execution_count": 19,
 129      "metadata": {},
 130      "output_type": "execute_result"
 131     }
 132    ],
 133    "source": [
 134     "fs = frozenset([1, 2, 3])\n",
 135     "fs"
 136    ]
 137   },
 138   {
 139    "cell_type": "code",
 140    "execution_count": 21,
 141    "metadata": {},
 142    "outputs": [
 143     {
 144      "data": {
 145       "text/plain": [
 146        "1"
 147       ]
 148      },
 149      "execution_count": 21,
 150      "metadata": {},
 151      "output_type": "execute_result"
 152     }
 153    ],
 154    "source": [
 155     "list(fs)[0]"
 156    ]
 157   },
 158   {
 159    "cell_type": "code",
 160    "execution_count": 23,
 161    "metadata": {},
 162    "outputs": [
 163     {
 164      "data": {
 165       "text/plain": [
 166        "frozenset({2, 3})"
 167       ]
 168      },
 169      "execution_count": 23,
 170      "metadata": {},
 171      "output_type": "execute_result"
 172     }
 173    ],
 174    "source": [
 175     "fs.difference(frozenset([1]))"
 176    ]
 177   },
 178   {
 179    "cell_type": "code",
 180    "execution_count": 47,
 181    "metadata": {},
 182    "outputs": [],
 183    "source": [
 184     "@lru_cache(maxsize=None)\n",
 185     "def recursive_valuefs(elements, weight_limit):\n",
 186     "    if len(elements) == 0:\n",
 187     "        return frozenset()\n",
 188     "    else:\n",
 189     "        this_element = list(elements)[0]\n",
 190     "        other_elements = elements.difference(frozenset([this_element]))\n",
 191     "        if this_element.weight > weight_limit:\n",
 192     "            return recursive_valuefs(other_elements, weight_limit)\n",
 193     "        else:\n",
 194     "            with_this = recursive_valuefs(other_elements, weight_limit - this_element.weight)\n",
 195     "            without_this = recursive_valuefs(other_elements, weight_limit)\n",
 196     "            items_with_this = with_this.union(frozenset([this_element]))\n",
 197     "            if sum(e.value for e in items_with_this) > sum(e.value for e in without_this):\n",
 198     "                return items_with_this\n",
 199     "            else:\n",
 200     "                return without_this"
 201    ]
 202   },
 203   {
 204    "cell_type": "code",
 205    "execution_count": 7,
 206    "metadata": {},
 207    "outputs": [],
 208    "source": [
 209     "def display_table(table, suppress_zero=True):\n",
 210     "    def formatted_row_element(e, suppress_zero):\n",
 211     "        if suppress_zero and e == 0:\n",
 212     "            return '   .'\n",
 213     "        else:\n",
 214     "            return '{:4d}'.format(e)\n",
 215     "    \n",
 216     "    \n",
 217     "    rows = max(k[0] for k in table.keys())\n",
 218     "    columns = max(k[1] for k in table.keys())\n",
 219     "    for r in range(rows+1):\n",
 220     "#         print(''.join('{:4d} '.format(table[r, c]) for c in range(columns + 1)))\n",
 221     "        print(' '.join(formatted_row_element(table[r, c], suppress_zero) for c in range(columns + 1)))"
 222    ]
 223   },
 224   {
 225    "cell_type": "code",
 226    "execution_count": 8,
 227    "metadata": {},
 228    "outputs": [],
 229    "source": [
 230     "def backtrace(table):\n",
 231     "    r = max(k[0] for k in table.keys())\n",
 232     "    c = max(k[1] for k in table.keys())\n",
 233     "    back_table = {}\n",
 234     "    while r > 0:\n",
 235     "        back_table[r, c] = table[r, c]\n",
 236     "        r, c = table[r, c]\n",
 237     "    return back_table"
 238    ]
 239   },
 240   {
 241    "cell_type": "code",
 242    "execution_count": 9,
 243    "metadata": {},
 244    "outputs": [],
 245    "source": [
 246     "def traced_table(base, backtrace):\n",
 247     "    return {k: base[k] if k in backtrace else 0 for k in base}"
 248    ]
 249   },
 250   {
 251    "cell_type": "code",
 252    "execution_count": 10,
 253    "metadata": {},
 254    "outputs": [],
 255    "source": [
 256     "def greedy_fill(elements, weight_limit):\n",
 257     "    return len(list(itertools.takewhile(lambda s: s < weight_limit, itertools.accumulate(sorted(e['weight'] for e in elements)))))"
 258    ]
 259   },
 260   {
 261    "cell_type": "code",
 262    "execution_count": 11,
 263    "metadata": {},
 264    "outputs": [],
 265    "source": [
 266     "def greedy_value_vpw(elements, weight_limit):\n",
 267     "    return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
 268     "                     itertools.accumulate(\n",
 269     "                         sorted((e for e in elements), key=lambda e: e['value'] / e['weight'], reverse=True),\n",
 270     "                         lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
 271     "               )[-1]['value']"
 272    ]
 273   },
 274   {
 275    "cell_type": "code",
 276    "execution_count": 12,
 277    "metadata": {},
 278    "outputs": [],
 279    "source": [
 280     "def greedy_value_w(elements, weight_limit):\n",
 281     "    return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
 282     "                     itertools.accumulate(\n",
 283     "                         sorted((e for e in elements), key=lambda e: e['weight']),\n",
 284     "                         lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
 285     "               )[-1]['value']"
 286    ]
 287   },
 288   {
 289    "cell_type": "code",
 290    "execution_count": 13,
 291    "metadata": {},
 292    "outputs": [],
 293    "source": [
 294     "elements = [{'weight': int(l.strip().split()[0]), 'value': int(l.strip().split()[1])} \n",
 295     "            for l in open('../../data/09-bags.txt')]\n",
 296     "weight_limit = 5000"
 297    ]
 298   },
 299   {
 300    "cell_type": "code",
 301    "execution_count": 33,
 302    "metadata": {},
 303    "outputs": [],
 304    "source": [
 305     "hashable_elements = frozenset(\n",
 306     "    Element(weight=e['weight'], value=e['value']) for e in elements\n",
 307     "    )"
 308    ]
 309   },
 310   {
 311    "cell_type": "code",
 312    "execution_count": 14,
 313    "metadata": {},
 314    "outputs": [
 315     {
 316      "data": {
 317       "text/plain": [
 318        "15"
 319       ]
 320      },
 321      "execution_count": 14,
 322      "metadata": {},
 323      "output_type": "execute_result"
 324     }
 325    ],
 326    "source": [
 327     "value, ct, br  = dp_count(elements, weight_limit)\n",
 328     "value"
 329    ]
 330   },
 331   {
 332    "cell_type": "code",
 333    "execution_count": 15,
 334    "metadata": {},
 335    "outputs": [
 336     {
 337      "data": {
 338       "text/plain": [
 339        "15"
 340       ]
 341      },
 342      "execution_count": 15,
 343      "metadata": {},
 344      "output_type": "execute_result"
 345     }
 346    ],
 347    "source": [
 348     "greedy_fill(elements, weight_limit)"
 349    ]
 350   },
 351   {
 352    "cell_type": "code",
 353    "execution_count": 39,
 354    "metadata": {},
 355    "outputs": [
 356     {
 357      "data": {
 358       "text/plain": [
 359        "15"
 360       ]
 361      },
 362      "execution_count": 39,
 363      "metadata": {},
 364      "output_type": "execute_result"
 365     }
 366    ],
 367    "source": [
 368     "len(recursive_count(hashable_elements, weight_limit))"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 16,
 374    "metadata": {},
 375    "outputs": [
 376     {
 377      "data": {
 378       "text/plain": [
 379        "2383"
 380       ]
 381      },
 382      "execution_count": 16,
 383      "metadata": {},
 384      "output_type": "execute_result"
 385     }
 386    ],
 387    "source": [
 388     "value, vt, vbr = dp_value(elements, weight_limit)\n",
 389     "value"
 390    ]
 391   },
 392   {
 393    "cell_type": "code",
 394    "execution_count": 17,
 395    "metadata": {},
 396    "outputs": [
 397     {
 398      "data": {
 399       "text/plain": [
 400        "1801"
 401       ]
 402      },
 403      "execution_count": 17,
 404      "metadata": {},
 405      "output_type": "execute_result"
 406     }
 407    ],
 408    "source": [
 409     "greedy_value_w(elements, weight_limit)"
 410    ]
 411   },
 412   {
 413    "cell_type": "code",
 414    "execution_count": 18,
 415    "metadata": {},
 416    "outputs": [
 417     {
 418      "data": {
 419       "text/plain": [
 420        "2300"
 421       ]
 422      },
 423      "execution_count": 18,
 424      "metadata": {},
 425      "output_type": "execute_result"
 426     }
 427    ],
 428    "source": [
 429     "greedy_value_vpw(elements, weight_limit)"
 430    ]
 431   },
 432   {
 433    "cell_type": "code",
 434    "execution_count": 48,
 435    "metadata": {},
 436    "outputs": [
 437     {
 438      "data": {
 439       "text/plain": [
 440        "frozenset({Element(weight=301, value=134),\n",
 441        "           Element(weight=314, value=166),\n",
 442        "           Element(weight=320, value=154),\n",
 443        "           Element(weight=336, value=190),\n",
 444        "           Element(weight=337, value=140),\n",
 445        "           Element(weight=340, value=172),\n",
 446        "           Element(weight=353, value=191),\n",
 447        "           Element(weight=356, value=153),\n",
 448        "           Element(weight=359, value=171),\n",
 449        "           Element(weight=365, value=177),\n",
 450        "           Element(weight=381, value=166),\n",
 451        "           Element(weight=382, value=185),\n",
 452        "           Element(weight=414, value=189),\n",
 453        "           Element(weight=434, value=195)})"
 454       ]
 455      },
 456      "execution_count": 48,
 457      "metadata": {},
 458      "output_type": "execute_result"
 459     }
 460    ],
 461    "source": [
 462     "recursive_valuefs(hashable_elements, weight_limit)"
 463    ]
 464   },
 465   {
 466    "cell_type": "code",
 467    "execution_count": 49,
 468    "metadata": {},
 469    "outputs": [
 470     {
 471      "data": {
 472       "text/plain": [
 473        "2383"
 474       ]
 475      },
 476      "execution_count": 49,
 477      "metadata": {},
 478      "output_type": "execute_result"
 479     }
 480    ],
 481    "source": [
 482     "sum(e.value for e in recursive_valuefs(hashable_elements, weight_limit))"
 483    ]
 484   },
 485   {
 486    "cell_type": "code",
 487    "execution_count": 52,
 488    "metadata": {},
 489    "outputs": [
 490     {
 491      "data": {
 492       "text/plain": [
 493        "305061"
 494       ]
 495      },
 496      "execution_count": 52,
 497      "metadata": {},
 498      "output_type": "execute_result"
 499     }
 500    ],
 501    "source": [
 502     "(len(elements) + 1) * 5001"
 503    ]
 504   },
 505   {
 506    "cell_type": "code",
 507    "execution_count": null,
 508    "metadata": {},
 509    "outputs": [],
 510    "source": []
 511   }
 512  ],
 513  "metadata": {
 514   "kernelspec": {
 515    "display_name": "Python 3",
 516    "language": "python",
 517    "name": "python3"
 518   },
 519   "language_info": {
 520    "codemirror_mode": {
 521     "name": "ipython",
 522     "version": 3
 523    },
 524    "file_extension": ".py",
 525    "mimetype": "text/x-python",
 526    "name": "python",
 527    "nbconvert_exporter": "python",
 528    "pygments_lexer": "ipython3",
 529    "version": "3.6.6"
 530   }
 531  },
 532  "nbformat": 4,
 533  "nbformat_minor": 2
 534 }