{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Challenge Notebook" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem: Given a knapsack with a total weight capacity and a list of items with weight w(i) and value v(i), determine which items to select to maximize total value.\n", "\n", "* [Constraints](#Constraints)\n", "* [Test Cases](#Test-Cases)\n", "* [Algorithm](#Algorithm)\n", "* [Code](#Code)\n", "* [Unit Test](#Unit-Test)\n", "* [Solution Notebook](#Solution-Notebook)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Constraints\n", "\n", "* Can we replace the items once they are placed in the knapsack?\n", " * No, this is the 0/1 knapsack problem\n", "* Can we split an item?\n", " * No\n", "* Can we get an input item with weight of 0 or value of 0?\n", " * No\n", "* Can we assume the inputs are valid?\n", " * No\n", "* Are the inputs in sorted order by val/weight?\n", " * Yes, if not we'd need to sort them first\n", "* Can we assume this fits memory?\n", " * Yes" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Test Cases\n", "\n", "* items or total weight is None -> Exception\n", "* items or total weight is 0 -> 0\n", "* General case\n", "\n", "
```\n",
"total_weight = 8\n",
"items\n",
"  v | w\n",
"  0 | 0\n",
"a 2 | 2\n",
"b 4 | 2\n",
"c 6 | 4\n",
"d 9 | 5\n",
"\n",
"max value = 13\n",
"items\n",
"  v | w\n",
"b 4 | 2\n",
"d 9 | 5 \n",
"```
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm\n", "\n", "Refer to the [Solution Notebook](http://nbviewer.jupyter.org/github/donnemartin/interactive-coding-challenges/blob/master/recursion_dynamic/knapsack_01/knapsack_solution.ipynb). If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Code" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "class Item(object):\n", "\n", " def __init__(self, label, value, weight):\n", " self.label = label\n", " self.value = value\n", " self.weight = weight\n", "\n", " def __repr__(self):\n", " return self.label + ' v:' + str(self.value) + ' w:' + str(self.weight)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Knapsack(object):\n", "\n", " def fill_knapsack(self, input_items, total_weight):\n", " # TODO: Implement me\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Unit Test" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**The following unit test is expected to fail until you solve the challenge.**" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# %load test_knapsack.py\n", "import unittest\n", "\n", "\n", "class TestKnapsack(unittest.TestCase):\n", "\n", " def test_knapsack_bottom_up(self):\n", " knapsack = Knapsack()\n", " self.assertRaises(TypeError, knapsack.fill_knapsack, None, None)\n", " self.assertEqual(knapsack.fill_knapsack(0, 0), 0)\n", " items = []\n", " items.append(Item(label='a', value=2, weight=2))\n", " items.append(Item(label='b', value=4, weight=2))\n", " items.append(Item(label='c', value=6, weight=4))\n", " items.append(Item(label='d', value=9, weight=5))\n", " total_weight = 8\n", " expected_value = 13\n", " results = knapsack.fill_knapsack(items, total_weight)\n", " self.assertEqual(results[0].label, 'd')\n", " self.assertEqual(results[1].label, 'b')\n", " total_value = 0\n", " for item in results:\n", " total_value += item.value\n", " self.assertEqual(total_value, expected_value)\n", " print('Success: test_knapsack_bottom_up')\n", "\n", " def test_knapsack_top_down(self):\n", " knapsack = KnapsackTopDown()\n", " self.assertRaises(TypeError, knapsack.fill_knapsack, None, None)\n", " self.assertEqual(knapsack.fill_knapsack(0, 0), 0)\n", " items = []\n", " items.append(Item(label='a', value=2, weight=2))\n", " items.append(Item(label='b', value=4, weight=2))\n", " items.append(Item(label='c', value=6, weight=4))\n", " items.append(Item(label='d', value=9, weight=5))\n", " total_weight = 8\n", " expected_value = 13\n", " self.assertEqual(knapsack.fill_knapsack(items, total_weight), expected_value)\n", " print('Success: test_knapsack_top_down')\n", "\n", "def main():\n", " test = TestKnapsack()\n", " test.test_knapsack_bottom_up()\n", " test.test_knapsack_top_down()\n", "\n", "\n", "if __name__ == '__main__':\n", " main()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solution Notebook\n", "\n", "Review the [Solution Notebook]() for a discussion on algorithms and code solutions." ] } ], "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.7.2" } }, "nbformat": 4, "nbformat_minor": 1 }