10 "import collections\n",
11 "from functools import lru_cache"
20 "def value_of(elements):\n",
21 " return sum(e['value'] for e in elements)\n",
23 "def weight_of(elements):\n",
24 " return sum(e['weight'] for e in elements)"
29 "execution_count": 32,
33 "Element = collections.namedtuple('Element', ['weight', 'value'])"
42 "def dp_count(elements, weight_limit):\n",
43 " count_table = {(0, j): 0 for j in range(weight_limit+1)}\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",
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",
58 " back_refs[i+1, remaining_weight] = (i, remaining_weight - element['weight'])\n",
60 " return count_table[len(elements), weight_limit], count_table, back_refs"
65 "execution_count": 37,
69 "@lru_cache(maxsize=None)\n",
70 "def recursive_count(elements, weight_limit):\n",
71 " if len(elements) == 0:\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",
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",
86 " return without_this"
95 "def dp_value(elements, weight_limit):\n",
96 " value_table = {(0, j): 0 for j in range(weight_limit+1)}\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",
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",
112 " back_refs[i+1, wl] = (i, wl - element['weight'])\n",
114 " return value_table[len(elements), weight_limit], value_table, back_refs"
119 "execution_count": 19,
125 "frozenset({1, 2, 3})"
128 "execution_count": 19,
130 "output_type": "execute_result"
134 "fs = frozenset([1, 2, 3])\n",
140 "execution_count": 21,
149 "execution_count": 21,
151 "output_type": "execute_result"
160 "execution_count": 23,
169 "execution_count": 23,
171 "output_type": "execute_result"
175 "fs.difference(frozenset([1]))"
180 "execution_count": 47,
184 "@lru_cache(maxsize=None)\n",
185 "def recursive_valuefs(elements, weight_limit):\n",
186 " if len(elements) == 0:\n",
187 " return frozenset()\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",
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",
200 " return without_this"
205 "execution_count": 7,
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",
214 " return '{:4d}'.format(e)\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)))"
226 "execution_count": 8,
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",
235 " back_table[r, c] = table[r, c]\n",
236 " r, c = table[r, c]\n",
242 "execution_count": 9,
246 "def traced_table(base, backtrace):\n",
247 " return {k: base[k] if k in backtrace else 0 for k in base}"
252 "execution_count": 10,
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)))))"
262 "execution_count": 11,
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",
276 "execution_count": 12,
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",
290 "execution_count": 13,
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"
301 "execution_count": 33,
305 "hashable_elements = frozenset(\n",
306 " Element(weight=e['weight'], value=e['value']) for e in elements\n",
312 "execution_count": 14,
321 "execution_count": 14,
323 "output_type": "execute_result"
327 "value, ct, br = dp_count(elements, weight_limit)\n",
333 "execution_count": 15,
342 "execution_count": 15,
344 "output_type": "execute_result"
348 "greedy_fill(elements, weight_limit)"
353 "execution_count": 39,
362 "execution_count": 39,
364 "output_type": "execute_result"
368 "len(recursive_count(hashable_elements, weight_limit))"
373 "execution_count": 16,
382 "execution_count": 16,
384 "output_type": "execute_result"
388 "value, vt, vbr = dp_value(elements, weight_limit)\n",
394 "execution_count": 17,
403 "execution_count": 17,
405 "output_type": "execute_result"
409 "greedy_value_w(elements, weight_limit)"
414 "execution_count": 18,
423 "execution_count": 18,
425 "output_type": "execute_result"
429 "greedy_value_vpw(elements, weight_limit)"
434 "execution_count": 48,
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)})"
456 "execution_count": 48,
458 "output_type": "execute_result"
462 "recursive_valuefs(hashable_elements, weight_limit)"
467 "execution_count": 49,
476 "execution_count": 49,
478 "output_type": "execute_result"
482 "sum(e.value for e in recursive_valuefs(hashable_elements, weight_limit))"
487 "execution_count": 52,
496 "execution_count": 52,
498 "output_type": "execute_result"
502 "(len(elements) + 1) * 5001"
507 "execution_count": null,
515 "display_name": "Python 3",
516 "language": "python",
524 "file_extension": ".py",
525 "mimetype": "text/x-python",
527 "nbconvert_exporter": "python",
528 "pygments_lexer": "ipython3",