{
 "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
}