--- /dev/null
+{
+ "cells": [
+ {
+ "cell_type": "code",
+ "execution_count": 31,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "import itertools\n",
+ "import collections\n",
+ "from functools import lru_cache"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 2,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def value_of(elements):\n",
+ " return sum(e['value'] for e in elements)\n",
+ " \n",
+ "def weight_of(elements):\n",
+ " return sum(e['weight'] for e in elements)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 32,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "Element = collections.namedtuple('Element', ['weight', 'value'])"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 3,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def dp_count(elements, weight_limit):\n",
+ " count_table = {(0, j): 0 for j in range(weight_limit+1)}\n",
+ " back_refs = {}\n",
+ "\n",
+ " for i, element in enumerate(elements):\n",
+ " for remaining_weight in range(weight_limit+1):\n",
+ " if element['weight'] > remaining_weight:\n",
+ " count_table[i+1, remaining_weight] = count_table[i, remaining_weight]\n",
+ " back_refs[i+1, remaining_weight] = (i, remaining_weight)\n",
+ " else:\n",
+ " count_table[i+1, remaining_weight] = max(\n",
+ " count_table[i, remaining_weight],\n",
+ " count_table[i, remaining_weight - element['weight']] + 1)\n",
+ " if count_table[i, remaining_weight] > count_table[i, remaining_weight - element['weight']] + 1:\n",
+ " back_refs[i+1, remaining_weight] = (i, remaining_weight)\n",
+ " else:\n",
+ " back_refs[i+1, remaining_weight] = (i, remaining_weight - element['weight'])\n",
+ "\n",
+ " return count_table[len(elements), weight_limit], count_table, back_refs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 37,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "@lru_cache(maxsize=None)\n",
+ "def recursive_count(elements, weight_limit):\n",
+ " if len(elements) == 0:\n",
+ " return []\n",
+ " else:\n",
+ " this_element = list(elements)[0]\n",
+ " other_elements = elements.difference(frozenset([this_element]))\n",
+ "# this_element = elements[0]\n",
+ "# other_elements = elements[1:]\n",
+ " if this_element.weight > weight_limit:\n",
+ " return recursive_count(other_elements, weight_limit)\n",
+ " else:\n",
+ " with_this = recursive_count(other_elements, weight_limit - this_element.weight)\n",
+ " without_this = recursive_count(other_elements, weight_limit)\n",
+ " if len(with_this) + 1 > len(without_this):\n",
+ " return [this_element] + with_this\n",
+ " else:\n",
+ " return without_this"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 5,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def dp_value(elements, weight_limit):\n",
+ " value_table = {(0, j): 0 for j in range(weight_limit+1)}\n",
+ " back_refs = {}\n",
+ " \n",
+ " for i, element in enumerate(elements):\n",
+ " for wl in range(weight_limit+1):\n",
+ " if element['weight'] > wl:\n",
+ " value_table[i+1, wl] = value_table[i, wl]\n",
+ " back_refs[i+1, wl] = (i, wl)\n",
+ "\n",
+ " else:\n",
+ " value_table[i+1, wl] = max(\n",
+ " value_table[i, wl],\n",
+ " value_table[i, wl - element['weight']] + element['value'])\n",
+ " if value_table[i, wl] > value_table[i, wl - element['weight']] + element['value']:\n",
+ " back_refs[i+1, wl] = (i, wl)\n",
+ " else:\n",
+ " back_refs[i+1, wl] = (i, wl - element['weight'])\n",
+ "\n",
+ " return value_table[len(elements), weight_limit], value_table, back_refs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 19,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "frozenset({1, 2, 3})"
+ ]
+ },
+ "execution_count": 19,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "fs = frozenset([1, 2, 3])\n",
+ "fs"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 21,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1"
+ ]
+ },
+ "execution_count": 21,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "list(fs)[0]"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 23,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "frozenset({2, 3})"
+ ]
+ },
+ "execution_count": 23,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "fs.difference(frozenset([1]))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 47,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "@lru_cache(maxsize=None)\n",
+ "def recursive_valuefs(elements, weight_limit):\n",
+ " if len(elements) == 0:\n",
+ " return frozenset()\n",
+ " else:\n",
+ " this_element = list(elements)[0]\n",
+ " other_elements = elements.difference(frozenset([this_element]))\n",
+ " if this_element.weight > weight_limit:\n",
+ " return recursive_valuefs(other_elements, weight_limit)\n",
+ " else:\n",
+ " with_this = recursive_valuefs(other_elements, weight_limit - this_element.weight)\n",
+ " without_this = recursive_valuefs(other_elements, weight_limit)\n",
+ " items_with_this = with_this.union(frozenset([this_element]))\n",
+ " if sum(e.value for e in items_with_this) > sum(e.value for e in without_this):\n",
+ " return items_with_this\n",
+ " else:\n",
+ " return without_this"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 7,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def display_table(table, suppress_zero=True):\n",
+ " def formatted_row_element(e, suppress_zero):\n",
+ " if suppress_zero and e == 0:\n",
+ " return ' .'\n",
+ " else:\n",
+ " return '{:4d}'.format(e)\n",
+ " \n",
+ " \n",
+ " rows = max(k[0] for k in table.keys())\n",
+ " columns = max(k[1] for k in table.keys())\n",
+ " for r in range(rows+1):\n",
+ "# print(''.join('{:4d} '.format(table[r, c]) for c in range(columns + 1)))\n",
+ " print(' '.join(formatted_row_element(table[r, c], suppress_zero) for c in range(columns + 1)))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 8,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def backtrace(table):\n",
+ " r = max(k[0] for k in table.keys())\n",
+ " c = max(k[1] for k in table.keys())\n",
+ " back_table = {}\n",
+ " while r > 0:\n",
+ " back_table[r, c] = table[r, c]\n",
+ " r, c = table[r, c]\n",
+ " return back_table"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 9,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def traced_table(base, backtrace):\n",
+ " return {k: base[k] if k in backtrace else 0 for k in base}"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 10,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def greedy_fill(elements, weight_limit):\n",
+ " return len(list(itertools.takewhile(lambda s: s < weight_limit, itertools.accumulate(sorted(e['weight'] for e in elements)))))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 11,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def greedy_value_vpw(elements, weight_limit):\n",
+ " return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
+ " itertools.accumulate(\n",
+ " sorted((e for e in elements), key=lambda e: e['value'] / e['weight'], reverse=True),\n",
+ " lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
+ " )[-1]['value']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 12,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "def greedy_value_w(elements, weight_limit):\n",
+ " return list(itertools.takewhile(lambda es: es['weight'] < weight_limit,\n",
+ " itertools.accumulate(\n",
+ " sorted((e for e in elements), key=lambda e: e['weight']),\n",
+ " lambda es, e: {'weight': es['weight'] + e['weight'], 'value': es['value'] + e['value']}))\n",
+ " )[-1]['value']"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 13,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "elements = [{'weight': int(l.strip().split()[0]), 'value': int(l.strip().split()[1])} \n",
+ " for l in open('../../data/09-bags.txt')]\n",
+ "weight_limit = 5000"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 33,
+ "metadata": {},
+ "outputs": [],
+ "source": [
+ "hashable_elements = frozenset(\n",
+ " Element(weight=e['weight'], value=e['value']) for e in elements\n",
+ " )"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 14,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "15"
+ ]
+ },
+ "execution_count": 14,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "value, ct, br = dp_count(elements, weight_limit)\n",
+ "value"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 15,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "15"
+ ]
+ },
+ "execution_count": 15,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "greedy_fill(elements, weight_limit)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 39,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "15"
+ ]
+ },
+ "execution_count": 39,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "len(recursive_count(hashable_elements, weight_limit))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 16,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2383"
+ ]
+ },
+ "execution_count": 16,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "value, vt, vbr = dp_value(elements, weight_limit)\n",
+ "value"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 17,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "1801"
+ ]
+ },
+ "execution_count": 17,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "greedy_value_w(elements, weight_limit)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 18,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2300"
+ ]
+ },
+ "execution_count": 18,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "greedy_value_vpw(elements, weight_limit)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 48,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "frozenset({Element(weight=301, value=134),\n",
+ " Element(weight=314, value=166),\n",
+ " Element(weight=320, value=154),\n",
+ " Element(weight=336, value=190),\n",
+ " Element(weight=337, value=140),\n",
+ " Element(weight=340, value=172),\n",
+ " Element(weight=353, value=191),\n",
+ " Element(weight=356, value=153),\n",
+ " Element(weight=359, value=171),\n",
+ " Element(weight=365, value=177),\n",
+ " Element(weight=381, value=166),\n",
+ " Element(weight=382, value=185),\n",
+ " Element(weight=414, value=189),\n",
+ " Element(weight=434, value=195)})"
+ ]
+ },
+ "execution_count": 48,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "recursive_valuefs(hashable_elements, weight_limit)"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 49,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "2383"
+ ]
+ },
+ "execution_count": 49,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "sum(e.value for e in recursive_valuefs(hashable_elements, weight_limit))"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": 52,
+ "metadata": {},
+ "outputs": [
+ {
+ "data": {
+ "text/plain": [
+ "305061"
+ ]
+ },
+ "execution_count": 52,
+ "metadata": {},
+ "output_type": "execute_result"
+ }
+ ],
+ "source": [
+ "(len(elements) + 1) * 5001"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "execution_count": null,
+ "metadata": {},
+ "outputs": [],
+ "source": []
+ }
+ ],
+ "metadata": {
+ "kernelspec": {
+ "display_name": "Python 3",
+ "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.6.6"
+ }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 2
+}
projects / summerofcode2018soln.git / blobdiff